MySQL索引结构之B-Tree和B+Tree数据结构的概念

1.B-Tree数据结构的概念以及动画演示

1.1.B-Tree数据结构的概念

B-Tree又称为B树结构，中文含义是多路平衡查找树。

相对于二叉树的数据结构来说，在B树的结构中，每个节点可以有多个分支，也就是多叉的概念，在二叉树中，每个节点下只能有2个子节点，而B树结构中一个节点下可以有很多个子节点，在查询效率这方面远远超越二叉树。

在B树结构中，每个节点下有多少个子节点是根据设置的最大度数来指定的，例如最大度数为5，那么就表示一个节点下最多能有5个子节点，也称为5阶的B数结构，无论有多少个子节点，每个节点中最多可以存储4个Key和5个指针，key就是具体的数据，指针数的计算方式是key的个数+1。

B数的结构图如下所示：

每个节点中最多可以存储4个key，每个节点上都有key的个数+1个指针，如根节点中有4个key，分别是50、60、70、80，在这个节点中有5个指针，这5个指针分别执指向下面的子节点。

• 小于50走第一个指针，指向子节点一的节点。
• 在50-60走第二个指针，指向子节点二的节点。
• 在60-70走第三个指针，指向子节点三的节点。
• 在70-80走第四个指针，指向子节点四的节点。
• 大于50走第五个指针，指向子节点五的节点。

无论一个节点中有多少个key，key的个数为n，那么指针的个数就是n+1个。

每个子节点下也是都有4个key的，继续往下深层划分，直到查询到我们需要的数据。

每一个key都包含了对应的表中数据，key的值就是我们做成索引字段对应的值。

在B树结构中，我们设置的key的个数为4时，当第五个key进来后，不会添加在对应的子节点中，而是通过分裂，选出中间元素然后再创建出一组子节点，将第五个key分配到新的子节点中。

1.2.通过一组数据演示B-Tree数据结构

动画显示B-Tree数据结构的网站：www.cs.usfca.edu/~galles/vis…

通过下面一组数据，演示B-Tree数据结构的分布、分裂过程。

50 60 70 80 22 85 101 65 99 120 135 125 128 138 35 38

1）插入50 60 70 80 四个数据，观察效果。

在左上角输入数据点击Insert即可在结构中写入四个数据，由于我们是5阶的数据结构，因此一个节点中可以有4个key、5个指针、5个子节点。

2）插入22这个数据，观察效果。

现在看到的这个节点中已经有4个key了，当再插入22这个数据后，由于该节点只能存4个key，此时就会分裂，取中间元素向上分裂，分裂出一个新的子节点。

中间元素指的是中间的那个key，这个key要向上分裂出一个节点，其余的四个key分裂成2个子节点。

现在的节点中有四个数据，再插入一个22之后，按照从小到大的顺序，22会放在50的前面，这样一来节点中就有5个key了，违背了5阶的概念，此时就会取中间元素，向上分裂，中间元素也就是中间数，60就是中间元素，60就向上分裂，形成一个新的节点，剩下的4个key也会分裂成两个子节点。

插入22这个数据，观察效果，就如刚刚说的，第五个key进入节点后，不满足5阶的概念，中间元素向上分裂，60是中间元素，直接向上分裂，形成一个新的节点，其余的4个key成为新节点中的子节点。

3）插入85和101这两个数据，观察效果。

85和101这两个数据比60要大，因此会写入到右侧的子节点中，现在右侧子节点key的个数是4个，还不用分裂。

4）插入65这个数据，观察效果。

65这个数据也是比60大，因此也会向右侧的节点中写入数据，但是此时该节点中就有5个key了，需要进行取中间元素然后向上分裂，将中间元素分裂出去，添加到上面的节点中，然后其余四个key对半分裂成两个子节点。

65写入后，中间元素就是80，从而向上分裂。

插入65这个数据，数据为80的key自动向上面的节点分裂，其余4个key对半分裂成新的子节点，如下图所示。

5）插入99和120这两个数据，观察效果。

99和120这两个数据比80要大，因此会写入到最右侧的子节点中，现在右侧子节点key的个数是4个，还不用分裂。

6）插入135这个数据，观察按效果。

135这个数据也是比80大，因此也会向最右侧的节点中写入数据，但是此时该节点中就有5个key了，需要进行取中间元素然后向上分裂，将中间元素分裂出去，添加到上面的节点中，然后其余四个key再对半分裂成两个子节点。

135写入后，中间元素就是101，从而向上分裂。

插入135这个数据，数据为101的key自动向上面的节点分裂，其余4个key对半分裂成新的子节点，如下图所示。

7）插入125和128这两个数据，观察效果。

125和128这两个数据比101要大，因此会写入到最右侧的子节点中，现在右侧子节点key的个数是4个，还不用分裂。

8）插入138这个数据，观察按效果。

138这个数据也是比101大，因此也会向最右侧的节点中写入数据，但是此时该节点中就有5个key了，需要进行取中间元素然后向上分裂，将中间元素分裂出去，添加到上面的节点中，然后其余四个key再对半分裂成两个子节点。

138写入后，中间元素就是125，从而向上分裂。

插入138这个数据，数据为125的key自动向上面的节点分裂，其余4个key对半分裂成新的子节点，如下图所示。

9）插入35和38这两个数据，观察效果。

35和38这两个数据比60要大，因此会写入到最左侧的子节点中，现在左侧子节点key的个数是4个，还不用分裂。

10）插入40这个数据，观察整体效果。

从现在的结构来看，最上面的节点已经有4个key了，左侧的子节点也有4个key了，如果左侧再插入一条数据，那么左侧的子节点就会取中间元素向上分裂，形成新的子节点，但是最上面的节点也有4个key了，如果左侧子节点向上分裂，势必也会导致最上面的节点再向上分裂。

插入40这个数据后，38就成为了中间元素，向上分裂，其他的四个key拆分成两个子节点，38进入最上面的节点后，80就成为中间元素，因此再向上分裂，其他的4个key拆分成两个子节点。

最终的数据结构如下所示。

2.B+Tree数据结构的概念以及动画演示

2.1.B+Tree数据结构的概念

B+Tree，B+树的结构与B树的结构类似，在B+树的结构中，所有的元素key都会出现在子节点中，节点中的元素key只是充当一个索引，每个元素key对应的数据都在子节点中存放。

如下图所示，这是一个2阶3指针的B+树结构图，上层的节点的key元素只有索引信息，最下层的子节点都会存放上层节点的key元素以及元素所包含的数据，最下层的子节点也称之为叶子节点。

例如30元素在子节点一中，子节点一中的30元素只含有索引信息，该子节点下的子节点也包含30这个元素的信息，在最下层的子节点中还包含了该元素的数据信息。

绿框部分的都是元素的索引信息，红框是叶子节点，包含了元素的数据信息。

在B+树中上面的子节点称为分页子节点，只包含索引的作用，而最下面的节点称为叶子节点，包含元素对应的数据信息。

在B+树的结构中，叶子节点形成了一个单向链表，每一个子节点都会通过一个指针指向下一个叶子节点 。

B+树与B树的结构有区别：

• 在B+树结构中，所有的数据都只出现在叶子节点，叶子节点会形成一个单向的链表。
• 非叶子节点仅仅起到索引数据的作用，具体的数据都在叶子节点存放。
• 而B树结构中，所有的节点都会存储数据。

2.2.通过一组数据演示B+Tree数据结构

动画显示B-Tree数据结构的网站：www.cs.usfca.edu/~galles/vis…

通过下面一组数据，演示B-Tree数据结构的分布、分裂过程。

100 150 200 250 356 420 288

1）插入100 150 200 250这四个数据，观察效果。

和B树的结构没有什么区别，请接着往下看。

2）插入356这个数据，观察效果。

现在该节点中已经有4个key元素了，再插入一条数据后，就违背了5阶的概念，然后取中间元素向上分裂。

此时插入356这个数据后，200就成为了中间元素，最终就会向上分裂，

分裂后，当前的数据结构如下所示，虽然200元素被向上分裂产生新的节点了，但是200这个元素在下面的叶子节点里也包含，这就是B+树与B数的区别，并且下面的叶子节点都会通过指针指向其他的叶子节点。

3）插入420这个数据，观察效果。

插入420这个数据，4230比200大，写入右侧子节点。

4）插入288这个数据，观察效果。

插入288数据，288比200大，写入右侧子节点，但是右侧子节点已经有4个key了，从而取中间元素向上分裂。

此时288这个数据就是中间元素，向上分裂，其余的4个key分裂成两个叶子节点，每个叶子节点都通过指针来指向其他的叶子节点。

2.3.MySQL中B+树索引的结构

在前面看到的B+树的结构是一个标准的B+树索引结构，但是MySQL对标准的B+树结构进行了优化，在原B+树的基础上，为相邻的叶子节点增加了一个指针，形成了有顺序指针的B+Tree结构，原来指针都是从小到大的方向指，MySQL优化后，小到大、大到小都可以互相指，提高了区间访问的性能，更利于排序。

MySQL优化的B+Tree结构中，每一个节点都依托于页之上，每一个页的大小为16K。

3.InnoDB存储引擎为什么采用B+Tree索引结构

InnoDB存储引擎为什么采用B+Tree索引结构：

• B+Tree索引结构相对于二叉树来说层级更少，每个子节点可以拥有多个key元素，二叉树结构是顺序检索的，效率很慢。
• 虽然红黑树可以解决二叉树顺序检索的问题，但是红黑树本质上也就是一个二叉树，效率依旧很慢。
• B-Tree索引结构中，无论是叶子节点还是非叶子节点，都需要存储数据，这样就会导致一页中存储的key元素减少，指针也会跟着减少，当数据量很大时，只能增加数结构的高度，最终导致性能很低，而B+Tree只有叶子节点会存储数据，非叶子节点保存的都是索引数据，并且叶子节点中的数据还回组成链表，无论是在查询还是排序还是范围查询，效率都远远换超过B-Tree结构。
• 相对于Hash索引，B+Tree支持范围匹配和排序操作，Hash索引不支持。