你真的了解Mysql索引底层原理吗？

　　导语
　　对于有千万行记录的数据表，查询速度和效率愈发重要，这直接影响到用户的体验。讲解Mysql索引底层原理之前，先来聊聊二叉树、红黑树、B树、B+树。
　　01  二叉树
　　相信有些许数据结构基础的小伙伴们对二叉树都有了解，其具体结构如下：
　　当采用二叉树作为索引时，并且把id作为索引并且id自增长时一个二叉树变成了一个单枝树，相当于链表查询，查询时间为O(n)，因此相当于没有建立索引，查询效率非常低。当查询9这个元素时的过程如下图所示：
　　02  红黑树
　　红黑树其实本质上也是一种二叉树，它对二叉树优化成了平衡二叉树，如下图所示：
　　红黑树的创建过程：
　　红黑树特点
　　从上图可以看出每当当前节点的左节点或者右节点超过两个时，红黑树会将其平衡。当使用这种数据结构存储MySQL索引时，会存在一个缺陷就是  树的高度太高，导致读取速度很慢  ，比如查找上图中的9这个节点，就需要查询5、8、9三次，由于MySQL数据是存储在磁盘上的，因此需要三次磁盘IO读取，当数据表数据量很大时，这就显得力不从心了，最糟糕要进行树的高度h次磁盘IO读取。
　　03  B树
　　通过以上所学知识我们知道，既然数据量大，从而导致树的高度不断增大，有什么方法可以限制树的高度呢？比如1000万条记录我能否将它浓缩成H<=4这样比较小的数呢？既然不能不能往纵向发展那就往横向发展，B树诞生了，如下图图所示：
　　B树特点
　　B树具有以下特点：
　　（1）叶节点具有相同的深度，叶节点的指针为空。
　　（2）所有索引元素不重复。
　　（3）节点中的数据索引从左到右递增排列。
　　它的存储结构如下图所示，每个节点的索引和数据都存储在一起。
　　B树查找原理
　　比如我们查找49这个元素，首先从根节点查找，一次性把所有的根节点node到内存RAM中(MySQL的限制大小为16KB)，然后在内存中查找49结果在15—56之间，因此找到指向15—56之间的指针，根据这个指针找到20----49这个大节点，然后将这个大节点Node到RAM中，然后在内存中找49，这样查询速度比红黑树大大提升。
　　04  B+树（B树的变种）
　　MySQL索引并没有采用B树而是采用B+树，B+树相对于B树具有以下特点：
　　（1）非叶子节点不存储data,只存储索引(冗余)，可以放更多的索引。
　　（2）叶子节点包含所有索引字段。
　　（3）叶子节点用指针连接，提高区间访问的性能。
　　B+树查找原理
　　在Mysql中，索引一般为bigint类型占 8个字节 ，对于索引后面的 指针占用6个字节 ，而Mysql给第一层大节点的限制内存大小为16KB,因此大概可以存储16KB/(6+8)B=1170个索引，同样第二层也可以存储1170个，而对于高度为3的B+树来说，假设第三层的索引和数据占用1KB大小，可以存放16KB/1KB=16个索引(加数据)，因此总共可以存储1170 x 1170 x 16 = 21,902,400个数据，2000多万条数据，令人诧异！
　　感谢大家的观看，记得点个关注哦~