MySQL数据库，详解索引原理(三)

平衡⼆叉树（AVL树）

平衡⼆叉树是⼀种特殊的⼆叉树，所以他也满⾜前⾯说到的⼆叉查找树的两个特性，同时还有⼀个特性：

它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。

平衡⼆叉树相对于⼆叉树来说，树的左右⽐较平衡，不会出现⼆叉树那样退化成链表的情况，不管怎么插⼊数据，最终通过⼀些调整，都能够保证树左右⾼度相差不⼤于1。

这样可以让查询速度⽐较稳定，查询中遍历节点控制在O(logN)范围内

如果数据都存储在内存中，采⽤AVL树来存储，还是可以的，查询效率⾮常⾼。不过我们的数据是存在磁盘中，⽤过采⽤这种结构，每个节点对应⼀个磁盘块，数据量⼤的时候，也会和⼆叉树⼀样，会导致树的⾼度变⾼，增加了io次数，显然⽤这种结构存储数据也是不可取的。

B-树

B杠树，千万不要读作B减树了，B-树在是平衡⼆叉树上进化来的，前⾯介绍的⼏种树，每个节点上⾯只有⼀个元素，⽽B-树节点中可以放多个元素，主要是为了降低树的⾼度。

⼀棵m阶的B-Tree有如下特性【特征描述的有点绕，看不懂的可以跳过，看后⾯的图】：

1. 每个节点最多有m个孩⼦，m称为b树的阶

2. 除了根节点和叶⼦节点外，其它每个节点⾄少有Ceil(m/2)个孩⼦

3. 若根节点不是叶⼦节点，则⾄少有2个孩⼦

4. 所有叶⼦节点都在同⼀层，且不包含其它关键字信息

5. 每个⾮终端节点包含n个关键字（健值）信息6. 关键字的个数n满⾜：ceil(m/2)-1 <= n <= m-1

7. ki(i=1,…n)为关键字，且关键字升序排序

8. Pi(i=1,…n)为指向⼦树根节点的指针。P(i-1)指向的⼦树的所有节点关键字均⼩于ki，但都⼤于k(i-1)

B-Tree结构的数据可以让系统⾼效的找到数据所在的磁盘块。为了描述B-Tree，⾸先定义⼀条记录为⼀个⼆元组[key, data] ，key为记录的键值，对应表中的主键值，data为⼀⾏记录中除主键外的数据。对于不同的记录，key值互不相同。

B-Tree中的每个节点根据实际情况可以包含⼤量的关键字信息和分⽀，如下图所⽰为⼀个

3阶的B-Tree：

每个节点占⽤⼀个盘块的磁盘空间，⼀个节点上有两个升序排序的关键字和三个指向⼦树根节点的指针，指针存储的是⼦节点所在磁盘块的地址。两个键将数据划分成的三个范围域，对应三个指针指向的⼦树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的⼦树的数据范围为⼩于17，P2指针指向的⼦树的数据范围为17~35，P3指针指向的⼦树的数据范围为⼤于35。

模拟查找关键字29的过程：

1. 根据根节点找到磁盘块1，读⼊内存。【磁盘I/O操作第1次】

2. ⽐较关键字29在区间（17,35），找到磁盘块1的指针P2 3. 根据P2指针找到磁盘块3，读⼊内存。【磁盘I/O操作第2次】

4. ⽐较关键字29在区间（26,30），找到磁盘块3的指针P2

5. 根据P2指针找到磁盘块8，读⼊内存。【磁盘I/O操作第3次】

6. 在磁盘块8中的关键字列表中找到关键字29

分析上⾯过程，发现需要3次磁盘I/O操作，和3次内存查找操作，由于内存中的关键字是⼀个有序表结构，可以利⽤⼆分法快速定位到⽬标数据，⽽3次磁盘I/O操作是影响整个BTree查找效率的决定因素。

B-树相对于avl树，通过在节点中增加节点内部数据的个数来减少磁盘的io操作。

上⾯我们说过mysql是采⽤页⽅式来读写数据，每页是16KB，我们⽤B-树来存储mysql的记录，每个节点对应mysql中的⼀页（16KB），假如每⾏记录加上树节点中的1个指针占

160Byte，那么每个节点可以存储1000（16KB/160byte）条数据，树的⾼度为3的节点⼤概可以存储（第⼀层1000+第⼆层 +第三层 ）10亿条记录，是不是⾮常惊讶，⼀个⾼度为3个B-树⼤概可以存储10亿条记录，我们从10亿记录中查找数据只需要3次io操作可以定位到⽬标数据所在的页，⽽页内部的数据又是有序的，然后将其加载到内存中⽤⼆分法查找，是⾮常快的。

可以看出使⽤B-树定位某个值还是很快的(10亿数据中3次io操作+内存中⼆分法)，但是也是有缺点的：B-不利于范围查找，⽐如上图中我们需要查找[15,36]区间的数据，需要访问7个磁盘块（1/2/7/3/8/4/9），io次数又上去了，范围查找也是我们经常⽤到的，所以b-树也不太适合在磁盘中存储需要检索的数据。