作者：高级臭虫调查员

如果是不了解网络的人，一定会惊叹于信息化时代发展的迅速、信息的传播。

目前互联网的信息处理速度达到万亿级，仅正月每12306秒的点击量就超过了双11的5倍，门票数量达到60亿次。

人们再也回不到那种凡事必须为父母而出门的时代了。

什么能让世界变快？ 什么使您能够快速处理数据？ 今天我们来谈谈MySQL索引的变化。

二叉树索引

索引是规则的数据存储结构。

在数据库刚刚兴起的时代，人们会考虑用类似词典目录的结构来实现数据的快速放置。

首先要解决的问题是秩序性。

有序性是索引的基础，有序的目录可以快速定位数据，快速定位索引在目录中的位置。

为了实现这一点，同样快速的散列函数不起作用。 由于无序，MySQL同样支持散列索引，但在大多数情况下不起作用。

人们自然地想到了二叉树。

二叉树是一种有序的数据存储结构，类似倒立生长的树型结构：

根据这样的结构，在数据表的某一列中创建这样结构的“目录”，各二叉树的节点指向具有该列值的记录地址，从而能够快速检索数据。

然而，二叉树虽然可以实现简单快捷的搜索，但仍然存在致命的弊端退化为——链表。

为什么二叉树会退化成链表？

这是因为，如果表列像递增或递减，则在编制索引时节点会偏向一侧形成一边的二叉树，最终与链表的结构完全一致。 但是，链表对快速定位数据完全没有帮助。 因此，基于这个致命的问题，人们对二叉树进行了改进。

红黑树索引

红黑树是平衡二叉树，是二叉树的变种。

红树的特征有很多，但其中最重要的是平衡。 也就是说，当树中的节点处于单边态势时，保证结构可以在一定程度上旋转，链表不会退化。

在Java 8中，HashMap的实现从原始的数组链表组合更改为数组红黑树组合，在一定程度上提高了数据的有序性，提高了查询性能。 从侧面也充分说明了红黑树比链表更适合数据检索。

但是，研究表明，红黑树解决了二叉树退化为链表的问题，但没有控制树的高度。

什么是树的高度？ 简单地说，就是木的层数。 红色的黑树无法控制树的高度，平衡节点的分配，但依然在向下延伸，最终树的结构越来越高。

如果某个元素位于树叶的节点处，该树的高度为20到30次左右，则需要搜索20到30次才能找到对应的元素。 这在效率至上的时代是绝对不允许的。 于是，人们又开始了新的探索之路。

B树索引

B树是一种可以设定一定高度的树结构，又称三叉平衡木，不仅具备平衡木的特性，还能有效控制树的高度。

b树索引在使用时将整个根节点加载到内存中，然后在根节点内随机搜索。

由于b树根据设定的最大深度(树的高度)调整每个节点可以容纳的元素数量，因此特定的b树可能会因最大深度而具有不同的结构。

每个节点的最大容量是多少？

/p>

内存与磁盘的IO交互有一个数据量限制，一般是4KBytes。因此，MySQL为了将节点加载到内存的效率最大化，设置一个文件的默认“分页大小”，它恰好是读取量限制的4倍，即16K：

实际上，MySQL并没有安全遵照B树来设计索引，而是采用了B树的变种——B+树。

B+树是一种改进的B树，与B树不同的地方有两点：

1、它将所有索引以外的数据域全部放到了叶子节点上，所以非叶子节点都只包含一个索引值和节点地址；

2、所有叶子节点都通过指针彼此相连。

这两点是B+树区别于B树的重要不同点。

B+树的叶子节点存储着所有表数据的地址或表数据其他的信息，这是为了可以让非叶子节点存储更多索引值，而叶子节点之间的指针，则是为了在进行范围搜索的时候，可以直接在叶子节点之间进行遍历或搜索，而不需要反复跨越多个父子节点，极大的节省了索引树搜索的时间。

虽然这些听起来不是那么重要，但是设想一下千万级别的数据处理场景就会发现，一点微小的改进，可能就会让系统的处理性能达到质的飞跃。

MySQL索引总结

从二叉树到平衡树，从红黑树再到B树，再到B+树，索引的结构在发生着变化。

人们不断的思考着更优秀的索引实现方案，也在不断地刷新着数据处理的速度极限。

任何知识的学习，都不能离开它们的设计思考与应用场景。从B+树的特性，我们看到了人们在选择这项技术之前所作出的努力。甚至可以说，它的每一个特性，小到有序性，大到树的高度、叶子节点的指针，都尤其存在的必要性，将这些特性分析透彻才能够真正理解索引的变迁史。

这就是MySQL索引的一些总结和思考，虽然并不能完全解释它的构造原理，但希望这篇文章可以给大家打开一个新的大门。

大家可以多多评论留言，祝技术之路越走越顺利！

往期精彩：

大话Java 8 Lambda 表达式（一）

束缚程序员工资的，从来不是什么算法和设计模式

那些还在B站发弹幕问“有人在吗”的人，求求你们别再犯二了

七夕节，来聊一聊程序员的浪漫

注释有多重要，看了这一篇你还不重新思考一下吗？