MySQL数据库索引原理及应用

Mysql中B+Tree索引的原理及索引的合理实践

1. { “MySQL 数据库索引原理及应用” , Topic: Remark: ” 干货” , Author: ” 宋达彬” , Deptartment: E-mail: Skill: ” 互联网业务研发中心 - 平台架构部” , ”[email protected]”, [ ”MySQL”, ”Mycat”, ”Web” ] }
2. { Name: “ 目录” , Content: [ ] } Chapter1: ” 索引和数据结构” , Chapter2: ” 索引的实现” , Chapter3: ” 索引性能分析” , Chapter4: ” 高性能索引策略”
3. { Chapter1: ” 索引和数据结构” , } Tip: “ 索引 (Index) 是帮助 MySQL 高效获取数据的数据结构” id name 0 Lillard 1 Bosh 3 Wade 23 James 24 Kobe 30 Curry 35 Durant 23 一个简单的索引 1 James 30 Bosh 0 3 24 35 Lillard Wade Kobe Durant AVL 树 { { 数据结构: 线性表 数据结构:平衡二叉树( 时间复杂度: O(n) } Curry 时间复杂度: O() } AVL 树)
4. { Chapter1: ” 索引和数据结构” , Question: “ 平衡二叉树 (AVL 树 ) 适合作为 MySQL 数据库索引吗?” } AVL 树 内排序 深度高 AVL 树的构建是一个内 排序的过程,必须全部 在内存中完成。数据量 大时会占用大量内存空 间。 平衡二叉树每个节点只 有 2 个孩子,扇出为 2 ,数据多时树深度大 ,导致更多磁盘 I/O , 查询变慢。 B-Tree 外排序 深度低 每次从外存中读取一部 分数据到内存中进行处 理。整个过程需要在内 存和外存之间进行数据 交换,可处理大量数据 。 采用平衡的多路查找树 结构。每个节点是存储 多个值的线性表,扩大 节点扇出,降低树深度 。
5. { Chapter1: ” 索引和数据结构” , Tip: “ 外存储结构索引相关的计算机组成原理知识” } 寻道时间:磁头对准磁道 Disk { name :“磁盘 I/O” properties : [ “ 寻道时间 + 旋转时间”, “ 每次至少读取一个扇区 (block)” , “ 时间消耗大” 磁盘存储 原理 ] 旋转时间:磁头旋转至扇区 } 外排序 { Memory 简单 RAM 工作原理 内排序 name :“内存存取” properties : [ “ 根据地址直接定位数据”, “ 无机械操作” , “ 速度快” ] } CPU { name :“磁盘预读” properties : [ “ 磁盘不是严格按需读取,而是顺序向后读取一定数据至内存”, “ 只需很少的旋转时间” , “ 预读长度为页( page )的整数倍(主存与磁盘之间以页为单位交换数据)” ] }
6. { ” 索引和数据结构” , “ 适合作为索引的数据结构的特点” } Chapter1: Tip: 较少磁盘 I/O 次 数 B-Tree { name :“ B-Tree 定义” properties : [ “ 数据记录为二元组 [key, data]” , “ 节点的最大扇出 d 为 B-Tree 的阶” , “ 非叶子节点由 d 个指针和 d-1 个 [key,data] 组成” , “ 节点中的 key 为有序序列”, “ 某个 key 的左指针指向节点的值小于该 key 值,右指针反之较 大” ] }
7. { Tip: id 3 5 8 9 10 12 13 15 17 26 28 29 30 35 36 60 65 75 79 87 90 99 ”MySQL 数据库索引的实现” , “ 基于外存的 B-Tree 索引结构” } Chapter2: name code Bosh A Wade B Park C Curry D Nash E Kidd F Cater G Allen H Tim I James J Blake K Gasol L Mike M Jones N Tony O Gary P Joe Q John R David S Rose T Kevin U Lee V create table tt( id int, name varchar(20), code char(1) primary key (id), key(code) ) ??? select * from tt where id = 29 【磁盘 I/O 三次】 磁盘块 磁盘块 1 索引列 17 35 Tim Jones Jones Tim I P1 其它列 N P3 P2 <17 >35 17~35 8 构建 B-Tree 索引 12 26 30 Park Park Kidd Kidd James James Mike Mike C P1 3 5 Bosh Bosh Wade Wade A B 磁盘块 5 F 磁盘块 2 P2 9 10 Curry Curry Nash Nash D E 磁盘块 6 J P3 P1 65 87 M 磁盘块 3 P2 P1 P3 Joe Joe Rose Rose Q T 磁盘块 4 P2 P3 13 15 28 29 36 60 75 79 90 99 Cater Cater Allen Allen Blake Blake Gasol Gasol Tony Tony Gary Gary John John David David Kevin Kevin Lee Lee G H 磁盘块 7 K L 磁盘块 8 B-Tree O P 磁盘块 9 R S 磁盘块 10 U V 磁盘块 11
8. { ”MySQL 数据库索引的实现” , “B+Tree” ,Type: ” 聚集索引” } Chapter2: Answer: ( B+Tree 是 B-Tree 的一种变种, MySQL 使用它来实现索引) B Tree B+Tree 1. 非叶子节点只存储键值 2. 数据记录在叶子节点中 3. 叶子节点间都有指针 磁盘块 1 聚集索引  Primary key P1 28 P2 磁盘块 2 P1 10 17 P1 5 8 9 Bosh Wade Wade Park Park Curry Curry Bosh A B C 磁盘块 4 D 10 12 13 15 F G 磁盘块 5 79 P3 P2 Nash Kidd Kidd Cater Cater Allen Allen Nash E 36 P3 P2 3 磁盘块 3 H 17 26 28 29 30 35 Tim James James Tim Blake Gasol Gasol Mike Mike Jones Jones Blake I J K 磁盘块 6 L M 磁盘块 7 B+Tree N 36 60 65 75 Tony Gary Gary Tony O P Joe Joe John John Q R 磁盘块 8 79 87 90 99 David Rose Rose Kevin Kevin Lee Lee David S T U 磁盘块 9 V
9. { ”MySQL 数据库索引的实现” , “B+Tree” ,Type: ”  助 索引 ” } Chapter2: Answer: 助 ??? select name from tt where code = ‘H’ 磁盘块 1 索引  key K P1 P2 叶子节点存 储主键值 P2 磁盘块 2 P1 A 3 B 5 C 8 D 9 D 磁盘块 3 O I P2 P1 P3 I J 17 26 K L M N 28 29 30 35 O P Q R 36 60 65 75 S T U V 79 87 90 99 磁盘块 5 磁盘块 6 磁盘块 7 磁盘块 8 磁盘块 9 磁盘块 1 聚集索引  Primary key P1 28 P2 磁盘块 2 磁盘块 3 10 17 P1 P3 P2 3 5 8 9 Bosh Wade Wade Park Park Curry Curry Bosh A B C 磁盘块 4 D P3 P2 E F G H 10 12 13 15 磁盘块 4 P1 S 17 26 28 29 30 35 Nash Kidd Kidd Cater Cater Allen Allen Nash Tim James James Tim Blake Gasol Gasol Mike Mike Jones Jones Blake F G 磁盘块 5 H I 79 P3 P2 10 12 13 15 E 36 J 磁盘块 6 K L M 磁盘块 7 N 36 60 65 75 Tony Gary Gary Tony O P Joe Joe John John Q R 磁盘块 8 79 87 90 99 David Rose Rose Kevin Kevin Lee Lee David S T U 磁盘块 9 V
10. { Chapter3: ” 索引性能分析” , Question: “ 一个磁盘块能存放多少个索引值?” } 磁盘块大小 16KB / 磁盘块 K1 索引占用空间 32B p0 p0 16B * 2 ( 冗余系 数) K2 p1 p1 ... p2 p2 ... Kn pn pn n = ? 16B 索引个数 500 每个节点能存储 500 个 值,即有 500 个子节点 K 索引值 ( long: 8B ) p p 指向子 点的指 (   8B )
11. { Chapter3: ” 索引性能分析” , Question: “B+Tree 树索引的平均磁盘 I/O 次数?” } 磁盘块 1 根节点常驻内存 K1 K2 Kn ... n个 磁盘块 1 K1 K2 ... 磁盘块 2 Kn K1 n个 K2 磁盘块 n ... Kn ... n个 n个 K1 K2 n个 2~3 次 I/0 磁盘块 n+1 K1 V1 K2 V2 n个 1500W ... 磁盘块 n+n Kn Vn ... n个 K1 V1 K2 V2 ... Kn Vn ... n个 n个 n*n*n 条记录 n = 500 * 0.5 = 250 (B+Tree 构建过程中可能有的节点没填充满 ) ... Kn
12. { ” 索引性能分析” , Chapter3: Question: “ 使用索引和不使用索引的性能差异?” } I/O 次数 使用索引: 不使用索引 : O(n) select * from tt where id = 26; 使用索引 不用索引 3 select * from tt where name = ‘James’; O(1) 2 1 0 1000 数据量 磁盘块 1 聚集索引  Primary key P1 28 P2 磁盘块 2 P1 磁盘块 3 10 17 P2 3 5 8 9 Bosh Bosh Wade Wade Park Park Curry Curry A B C 磁盘块 4 D P1 P3 17 26 28 29 30 35 Nash Nash Kidd Kidd Cater Cater Allen Allen Tim Tim James James Blake Blake Gasol Gasol Mike Mike Jones Jones F G 磁盘块 5 H I 79 P3 P2 10 12 13 15 E 36 J 磁盘块 6 K L M 磁盘块 7 N 36 60 65 75 Tony Tony Gary Gary O P Joe Joe John John Q R 磁盘块 8 79 87 90 99 David David Rose Rose Kevin Kevin Lee Lee S T U 磁盘块 9 V
13. { Chapter4: ” 高性能索引策略” , Answer: [ ” 合理建索引” , ” 用上索引” ] } 建索引 用索引 1. 全 匹配。如     key(a) 1. 常用   条件字段建索引;  2.   度 低的列不用建索引,如性  ,状  ; 3. 多列索引,查询条件中同时用到多个列,将选择度高 的列放在左边 ; 4. 禁止冗余索引。 key(a,b) 和 key(a), 后者冗余; 5. 禁止重复索引。 primary key(a) 和 key(a), 后者重复; 6. 索引数量控制在 5 个以内; ✔ where a = v ✘ where a != v ✘ where b = v ✘ a like ‘%v’ 2. 匹配最左前缀。如 key(a,b) ✔ where a = v 3. 匹配列前缀。如 key(a) ✔ a like ‘v%’ 4. 匹配范围列。如 index(a) w✔ here a > v;where a between v1 and v2
14. Q&A Thanks!