MySQL为什么要使用B+树索引

⽬录

搞懂这个问题之前，我们⾸先来看⼀下MySQL表的存储结构，再分别对⽐⼆叉树、多叉树、B树和B+树的区别就都懂了。

MySQL的存储结构

表存储结构

单位：表>段>区>页>⾏

在数据库中， 不论读⼀⾏，还是读多⾏，都是将这些⾏所在的页进⾏加载。也就是说存储空间的基本单位是页。⼀个页就是⼀棵树B+树的节点，数据库I/O操作的最⼩单位是页，与数据库相关的内容都会存储在页的结构⾥。

B+树索引结构

1. 在⼀棵B+树中，每个节点为都是⼀个页，每次新建节点的时候，就会申请⼀个页空间2. 同⼀层的节点为之间，通过页的结构构成了⼀个双向链表

3. ⾮叶⼦节点为，包括了多个索引⾏，每个索引⾏⾥存储索引键和指向下⼀层页⾯的指针

4. 叶⼦节点为，存储了关键字和⾏记录，在节点内部（也就是页结构的内部）记录之间是⼀个单向的链表

B+树页节点结构

有以下⼏个特点

1. 将所有的记录分成⼏个组， 每组会存储多条记录，

2. 页⽬录存储的是槽（slot），槽相当于分组记录的索引，每个槽指针指向了不同组的最后⼀个记录3. 我们通过槽定位到组，再查看组中的记录

页的主要作⽤是存储记录，在页中记录以单链表的形式进⾏存储。

单链表优点是插⼊、删除⽅便，缺点是检索效率不⾼，最坏的情况要遍历链表所有的节点。因此页⽬录中提供了⼆分查找的⽅式，来提⾼记录的检索效率。

B+树的检索过程

我们再来看下B+树的检索过程

1. 从B+树的根开始，逐层找到叶⼦节点。

2. 找到叶⼦节点为对应的数据页，将数据叶加载到内存中，通过页⽬录的槽采⽤⼆分查找的⽅式先找到⼀个粗略的记录分组。3. 在分组中通过链表遍历的⽅式进⾏记录的查找。

为什么要⽤B+树索引

数据库访问数据要通过页，⼀个页就是⼀个B+树节点，访问⼀个节点相当于⼀次I/O操作，所以越快能找到节点，查找性能越好。B+树的特点就是够矮够胖，能有效地减少访问节点次数从⽽提⾼性能。下⾯，我们来对⽐⼀个⼆叉树、多叉树、B树和B+树。

⼆叉树

⼆叉树是⼀种⼆分查找树，有很好的查找性能，相当于⼆分查找。

但是当N⽐较⼤的时候，树的深度⽐较⾼。数据查询的时间主要依赖于磁盘IO的次数，⼆叉树深度越⼤，查找的次数越多，性能越差。最坏的情况是退化成了链表，如下图

为了让⼆叉树不⾄于退化成链表，⼈们发明了AVL树（平衡⼆叉搜索树）：任何结点的左⼦树和右⼦树⾼度最多相差1

多叉树

多叉树就是节点可以是M个，能有效地减少⾼度，⾼度变⼩后，节点变少I/O⾃然少，性能⽐⼆叉树好了

B树

B树简单地说就是多叉树，每个叶⼦会存储数据，和指向下⼀个节点的指针。例如要查找9，步骤如下

1. 我们与根节点的关键字 (17，35）进⾏⽐较，9 ⼩于 17 那么得到指针 P1；

2. 按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；3. 按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

B+树

B+树是B树的改进，简单地说是：只有叶⼦节点才存数据，⾮叶⼦节点是存储的指针；所有叶⼦节点构成⼀个有序链表

B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更⼩，如果把所有同⼀内部节点的关键字存放在同⼀盘块中，那么盘块所能容纳的关键字数量也越多，⼀次性读⼊内存的需要查找的关键字也就越多，相对IO读写次数就降低了例如要查找关键字16，步骤如下

1. 与根节点的关键字 (1，18，35) 进⾏⽐较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）2. 找到磁盘块 2，关键字为（1，8，14），因为 16 ⼤于 14，所以得到指针 P3（指向磁盘块 7）

3. 找到磁盘块 7，关键字为（14，16，17），然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据。B+树与B树的不同：

1. B+树⾮叶⼦节点不存在数据只存索引，B树⾮叶⼦节点存储数据

2. B+树查询效率更⾼。B+树使⽤双向链表串连所有叶⼦节点，区间查询效率更⾼（因为所有数据都在B+树的叶⼦节点，扫描数据库 只需扫⼀遍叶⼦结点就⾏了），但是B树则需要通过中序遍历才能完成查询范围的查找。

3. B+树查询效率更稳定。B+树每次都必须查询到叶⼦节点才能找到数据，⽽B树查询的数据可能不在叶⼦节点，也可能在，这样就会造成查询的效率的不稳定4. B+树的磁盘读写代价更⼩。B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更⼩，通常B+树矮更胖，⾼度⼩查询产⽣的I/O更少。这就是MySQL使⽤B+树的原因，就是这么简单！