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

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