此文章主要回答以下问题：
1 、索引数据结构演变
2 、mysql索引数据结构
mysql索引的演变
线性结构：首先不得不提的是线性结构，无论是数组还是链表检索多的数据，其性能降低，这样逐条检索的效率不用多说
线性结构.jpg
二叉树搜索树：二叉树搜索树有效的降低了检索数据的时间复杂度
二叉搜索树.jpg
但是当二叉排序树的不平衡性导致时间复杂度大大下降
二叉搜索树特.jpg
此时又有了AVL树，类似于红黑树下面按照红黑树来说
红黑二叉查找树：红黑树的宁一种定义是含有红黑链接并且满足下列条件的二叉查找树：
- 红链接均为做链接；
- 没有任何一个节点同时拥有和二条红链接相连；
- 该树是完美平衡的，即任意空连接到根节点的的路劲上的黑链接数量相同。
可以简单的理解为就是红黑树就是加入自平衡的二叉树
红黑树.jpg
数据库是一个庞大存储，随着数据量的增大，红黑树将会进行纵向的增加，性能也会大大的降低
B树：B树就是解决了纵向增大的问题，将每个节点的存储的数量增加，有效的降低树深度。然而每个节点的度不可能无限制的增加，这里就要设计到计算机原理中一次IO操作所能读取的4k，所以mysql的设计人员将每个节点的大小为4k
度为4的B树
B树.jpg
插入第四个**数据
B树1.jpg
B+树： B+树其实就是B树的一个变种，B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。（操作系统空间局部性原理：在最近的将来用到的信息很可能与现在正在使用的信息在空间地址上是邻近的），所以每次IO即使读取一个数据也会将邻近的数据读取出来，这应该是长久的经验积累而来，所以B+树的叶节点是相连的
mysql索引数据结构
MyISAM的索引方式也叫做“非聚集”的
MyisamPrimarykey.jpg
InnoDB存储引擎采用的是B+树作为索引结构
InnoDB聚集索引（主键）.png
mysql聚集索引，从问题入手
问题1、为什么Innodb表需要主键？
- 1）innodb表数据文件都是基于主键索引组织的，没有主键，mysql寻找一列唯一的作为主键，如果没有就会建立一列隐藏的主键，我们是看不到，所以mysql
- 2）其他类型索引都要引用主键索引；
问题2、为什么不建议Innodb表主键设置过长？
- 1）因为辅助索引都保存引用主键索引，过长的主键索引使辅助索引变得过大；
- 2） 因为字符串比较都是根据字符，如果使用UUID比较耗时会增加
问题3：为什么建议InnoDB表主键是单调递增？
- 如果InnoDB表主键是单调递增的，可以使用改进后的B+tree分裂策略，显著减少B-Tree分裂次数和数据迁移，从而提高数据插入效率。
不仅如此，它还大大提高索引页空间利用率。
叶子节点连续递增
mysql二级索引
Mysql二级索引.png
二级索引叶子节点存储的不再是行的物理位置，而是主键值。
通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据叶，再通过数据叶中的Page Directory找到数据行。
推荐一个网站：数据结构可视化里面包含各种数据结构可视化显示，能够其过程动态展示，良心推荐
重点：参考资料这篇博客是是你必须要读的文章，无论你是看懂我这篇文章没有，还是觉得我这篇文章多差，都建议你花至少半小时详细读
参考资料：
MySQL索引背后的数据结构及算法原理
·
网友评论