| 失效链接处理 |
|
MySQL 索引：索引为什么使用 B+树？ PDF 下载
本站整理下载：
相关截图：
主要内容：
⼆叉查找树(BST，Binary Search Tree)，也叫⼆叉排序树，在⼆叉树的基础上需
要满⾜：任意节点的左⼦树上所有节点值不⼤于根节点的值，任意节点的右⼦树
上所有节点值不⼩于根节点的值。如下是⼀颗 BST(图⽚来源)。
当需要快速查找时，将数据存储在 BST 是⼀种常⻅的选择，因为此时查询时间取
决于树⾼，平均时间复杂度是 O(lgn)。然⽽，BST**可能⻓歪⽽变得不平衡**，
如下图所示(图⽚来源)，此时 BST 退化为链表，时间复杂度退化为 O(n)。
为了解决这个问题，引⼊了平衡⼆叉树。
AVL 树是严格的平衡⼆叉树，所有节点的左右⼦树⾼度差不能超过 1；AVL 树查
找、插⼊和删除在平均和最坏情况下都是 O(lgn)。
AVL 实现平衡的关键在于旋转操作：插⼊和删除可能破坏⼆叉树的平衡，此时需
要通过⼀次或多次树旋转来重新平衡这个树。当插⼊数据时，最多只需要 1 次旋
转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL 需要维护从被删
除节点到根节点这条路径上所有节点的平衡，旋转的量级为 O(lgn)。
由于旋转的耗时，AVL**树在删除数据时效率很低**；在删除操作较多时，维护
平衡所需的代价可能⾼于其带来的好处，因此 AVL 实际使⽤并不⼴泛。
与 AVL 树相⽐，红⿊树并不追求严格的平衡，⽽是⼤致的平衡：只是确保从根到
叶⼦的最⻓的可能路径不多于最短的可能路径的两倍⻓。从实现来看，红⿊树最
⼤的特点是每个节点都属于两种颜⾊(红⾊或⿊⾊)之⼀，且节点颜⾊的划分需要
满⾜特定的规则(具体规则略)。红⿊树示例如下（图⽚来源）：
与 AVL 树相⽐，红⿊树的查询效率会有所下降，这是因为树的平衡性变差，⾼度
更⾼。但红⿊树的删除效率⼤⼤提⾼了，因为红⿊树同时引⼊了颜⾊，当插⼊或
删除数据时，只需要进⾏ O(1)次数的旋转以及变⾊就能保证基本的平衡，不需要
像 AVL 树进⾏ O(lgn)次数的旋转。总的来说，红⿊树的统计性能⾼于 AVL。
因此，在实际应⽤中，AVL 树的使⽤相对较少，⽽红⿊树的使⽤⾮常⼴泛。例
如，Java 中的 TreeMap 使⽤红⿊树存储排序键值对；Java8 中的 HashMap 使
⽤链表+红⿊树解决哈希冲突问题(当冲突节点较少时，使⽤链表，当冲突节点较
多时，使⽤红⿊树)。
对于数据在内存中的情况（如上述的 TreeMap 和 HashMap），红⿊树的表现是
⾮常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如**MySQL**等数
据库），红⿊树并不擅⻓，因为红⿊树⻓得还是太⾼了。当数据在磁盘中时，磁
盘 IO 会成为最⼤的性能瓶颈，设计的⽬标应该是尽量减少 IO 次数；⽽树的⾼度
越⾼，增删改查所需要的 IO 次数也越多，会严重影响性能。
B 树也称 B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，
与⼆叉树相⽐，B 树的每个⾮叶节点可以有多个⼦树。 因此，当总节点数量相同
时，B 树的⾼度远远⼩于 AVL 树和红⿊树(B 树是⼀颗“矮胖⼦”)，磁盘 IO 次数
⼤⼤减少。
定义 B 树最重要的概念是阶数(Order)，对于⼀颗 m 阶 B 树，需要满⾜以下条
件：
每个节点最多包含 m 个⼦节点。
如果根节点包含⼦节点，则⾄少包含 2 个⼦节点；除根节点外，每个⾮叶节
点⾄少包含 m/2 个⼦节点。
拥有 k 个⼦节点的⾮叶节点将包含 k - 1 条记录。
所有叶节点都在同⼀层中。
可以看出，B 树的定义，主要是对⾮叶结点的⼦节点数量和记录数量的限制。
下图是⼀个 3 阶 B 树的例⼦（图⽚来源）：
B 树的优势除了树⾼⼩，还有对访问局部性原理的利⽤。所谓局部性原理，是指
当⼀个数据被使⽤时，其附近的数据有较⼤概率在短时间内被使⽤。B 树将键相
近的数据存储在同⼀个节点，当访问其中某个数据时，数据库会将该整个节点读
到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，⽆需进⾏
磁盘 IO；换句话说，B 树的缓存命中率更⾼。
B 树在数据库中有⼀些应⽤，如 mongodb 的索引使⽤了 B 树结构。但是在很多
数据库应⽤中，使⽤了是 B 树的变种 B+树。
B+树也是多路平衡查找树，其与 B 树的区别主要在于：
B 树中每个节点（包括叶节点和⾮叶节点）都存储真实的数据，B+树中只有
叶⼦节点存储真实的数据，⾮叶节点只存储键。在 MySQL 中，这⾥所说的
真实数据，可能是⾏的全部数据（如 Innodb 的聚簇索引），也可能只是⾏
的主键（如 Innodb 的辅助索引），或者是⾏所在的地址（如 MyIsam 的⾮
聚簇索引）。
B 树中⼀条记录只会出现⼀次，不会重复出现，⽽ B+树的键则可能重复重现
——⼀定会在叶节点出现，也可能在⾮叶节点重复出现。
B+树的叶节点之间通过双向链表链接。
B 树中的⾮叶节点，记录数⽐⼦节点个数少 1；⽽ B+树中记录数与⼦节点个
数相同。
由此，B+树与 B 树相⽐，有以下优势：
更少的 IO 次数：B+树的⾮叶节点只包含键，⽽不包含真实数据，因此每个
节点存储的记录个数⽐ B 数多很多（即阶 m 更⼤），因此 B+树的⾼度更
低，访问时所需要的 IO 次数更少。此外，由于每个节点存储的记录数更
多，所以对访问局部性原理的利⽤更好，缓存命中率更⾼。
更适于范围查询：在 B 树中进⾏范围查询时，⾸先找到要查找的下限，然后
对 B 树进⾏中序遍历，直到找到查找的上限；⽽ B+树的范围查询，只需要
对链表进⾏遍历即可。
更稳定的查询效率：B 树的查询时间复杂度在 1 到树⾼之间(分别对应记录在
根节点和叶节点)，⽽ B+树的查询复杂度则稳定为树⾼，因为所有数据都在
叶节点。
B+树也存在劣势：由于键会重复出现，因此会占⽤更多的空间。但是与带来的性
能优势相⽐，空间劣势往往可以接受，因此 B+树的在数据库中的使⽤⽐ B 树更
加⼴泛。
前⾯说到，B 树/B+树与红⿊树等⼆叉树相⽐，最⼤的优势在于树⾼更⼩。实际
上，对于 Innodb 的 B+索引来说，树的⾼度⼀般在 2-4 层。下⾯来进⾏⼀些具体
的估算。
树的⾼度是由阶数决定的，阶数越⼤树越矮；⽽阶数的⼤⼩⼜取决于每个节点可
以存储多少条记录。Innodb 中每个节点使⽤⼀个⻚(page)，⻚的⼤⼩为 16KB，
其中元数据只占⼤约 128 字节左右(包括⽂件管理头信息、⻚⾯头信息等等)，⼤
多数空间都⽤来存储数据。
对于⾮叶节点，记录只包含索引的键和指向下⼀层节点的指针。假设每个⾮
叶节点⻚⾯存储 1000 条记录，则每条记录⼤约占⽤ 16 字节；当索引是整型
或较短的字符串时，这个假设是合理的。延伸⼀下，我们经常听到建议说索
引列⻓度不应过⼤，原因就在这⾥：索引列太⻓，每个节点包含的记录数太
少，会导致树太⾼，索引的效果会⼤打折扣，⽽且索引还会浪费更多的空
间。
对于叶节点，记录包含了索引的键和值(值可能是⾏的主键、⼀⾏完整数据
等，具体⻅前⽂)，数据量更⼤。这⾥假设每个叶节点⻚⾯存储 100 条记录
(实际上，当索引为聚簇索引时，这个数字可能不⾜ 100；当索引为辅助索引
时，这个数字可能远⼤于 100；可以根据实际情况进⾏估算)。
对于⼀颗 3 层 B+树，第⼀层(根节点)有 1 个⻚⾯，可以存储 1000 条记录；第⼆
层有 1000 个⻚⾯，可以存储 10001000 条记录；第三层(叶节点)有 10001000 个
⻚⾯，每个⻚⾯可以存储 100 条记录，因此可以存储 10001000100 条记录，即
1 亿条。⽽对于⼆叉树，存储 1 亿条记录则需要 26 层左右。
最后，总结⼀下各种树解决的问题以及⾯临的新问题：
⼆叉查找树(BST) ：解决了排序的基本问题，但是由于⽆法保证平衡，可能
退化为链表；
平衡⼆叉树(AVL) ：通过旋转解决了平衡的问题，但是旋转操作效率太低；
红⿊树 ：通过舍弃严格的平衡和引⼊红⿊节点，解决了 AVL 旋转效率过低
的问题，但是在磁盘等场景下，树仍然太⾼，IO 次数太多；
B 树 ：通过将⼆叉树改为多路平衡查找树，解决了树过⾼的问题；
B+树 ：在 B 树的基础上，将⾮叶节点改造为不存储数据的纯索引节点，进
⼀步降低了树的⾼度；此外将叶节点使⽤指针连接成链表，范围查询更加⾼
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
