MySQL突击-索引数据结构

我们在日常开发中，SQL优化是重中之重，我们大部分时候都是按照那几条基本的优化原则去进行优化，但是遇到一些复杂的业务场景SQL，可能就需要我们去做分析，而这时候我们就需要了解索引的底层原理以及数据结构，以便我们更好的分析优化SQL。

什么是索引？

索引是帮助MySQL高效获取数据的排好序的数据结构。这是MySQL官方对索引的一种定义，而通过这种定义，我们可以总结出：索引就是一种数据结构，是一种已经排好序的方便我们快速查找数据的一种数据结构。

重点词汇：排好序的

我们都知道，MySQL索引使用的是B+Tree，那么多数据结构，为啥MySQL最终选择使用B+Tree呢?

几种常见的索引数据结构

二叉树

什么是二叉树？

二叉树是每个节点最多有两个子树的树结构。

二叉树的结构图

MySQL为何不使用二叉树？

在实际开发建表时，为了提升性能，我们一般都会要求每个表都要创建自增的主键索引。结合图中的二叉树结构，当二叉树节点是依次递增的情况下，整体结构其实就相当于是一个链表。而且实际业务场景中，MySQL一般存储的数据较多，在使用二叉树时，数据越多，树的高度就越高，那查找效率也就越来约低。此时如果我们需要查找图中的0007，那就需要从0001开始遍历，这种效率显而易见。

红黑树

什么是红黑树？

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

红黑树的数据结构图

MySQL为何不使用红黑树？

红黑树虽然是平衡二叉树，但它依然存在树高的问题，数据量越多，红黑树的高度也会随之变高，树的高度也变得不可控，查找一次数据遍历的次数也会越来越多，大数据量依然会成为一个瓶颈(IO操作频繁)。

B-Tree

什么是B树？

B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。

B树的特点

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

B树的数据结构图 MySQL为何不使用B-Tree？

从B树的数据结构图可以看出，B树在每个索引下都存储了data，在节点大小相同得情况下(MySql设置每个节点默认为16K)，若每个节点索引+data大小为1K，那每个节点可以存储的元素为16个,在这种情况下，随着MySQL数据的不断增多，那树得高度也就更高，树高依然回成为MySQL的性能瓶颈。

B树的变种：B+Tree

B+Tree的特点：

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能

B+Tree的数据结构图

B+Tree的优点：

从B+Tree的数据结构图中我们可以看出，它将B树的data全部放到了叶子节点中，非叶子节点不再存储data。节点大小依然为16KB，我们的一个主键索引正常是不会特别大，此处我们以主键为bigint类型，大小为8B ，两个索引之间(图中白色的方块)存储的是下一个节点的磁盘地址，大小大概为6B，按照这两个大小来计算一个16KB的节点可以存储1170个元素。图中第一第二个节点都可以存储1170个元素，第三个节点因为存储了data数据(索引所在行的所有数据)，占用的空间比较大，我们假设为1K，第三个节点可以存储16个元素，当整个B+Tree存满之后，最终图中的第三个节点也就是叶子节点总共可以存储1170*1170*16=21,902,400个元素，可以看出，B+Tree在只有三层树高的情况下可以存储两千多万的数据。

上边我们分析了几种常见的索引数据结构，也通过B+Tree的一个数据量存储计算，直观的看出了B+Tree的优点，MySQL最终也是使用B+Tree作为索引的数据结构。很好的理解了索引的数据结构，可以帮助我们日后更好的优化我们的SQL性能。