Mysql 索引底层数据结构和算法

Hash表

二叉树

红黑树

B树

B+树

索引（index）是帮助MySQL高效获取数据的一种有序数据结构。索引是存储到表空间中，当我们的 sql 中的where条件用到索引的时候，会在存储引擎层就过滤出数据来，如果不走索引，则需要在server层过滤。存储层过滤的性能比在server层更好。

常用的索引结构有：Hash表，二叉树，平衡二叉查找树（红黑树是一个近似平衡二叉树），B树，B+树。

数据结构在线演示网站：Data Structure Visualization

Mysql5.7之后选用B+树作为默认的索引结构，接下来，介绍各种数据结构存在的优缺点。

我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；

原理

　A. 事先将索引通过 hash算法后得到的hash值(即磁盘文件指针）存到hash表中。

　B. 在进行查询时，将索引通过hash算法，得到hash值，与hash表中的hash值比对。通过磁盘文件指针，只要一次磁盘IO就能找到要的值。

优点：

缺点：

特点：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。二叉树的检索复杂度和树高相关：理想状态下效率可以达到O(logn)

缺点：在某些特定的情况下，二叉树有可能退化成单链表的，此时会进行全表扫描，并且元素的查找效率也会明显的下降。

红黑树是一个近似平衡的二叉树。

平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。

缺点：

时间复杂度和树高相关：树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作【瓶颈】。
- 磁盘每次寻道时间为10ms，在表数据量大时，对响应时间要求高的场景下，查询性能就会出现瓶颈。举例：1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s
平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率极差。
数据量大的情况下，索引存储空间占用巨大

减少耗时的IO操作，就要尽量降低树的高度，把二叉树，变为多叉树。每个节点存储多个元素，在每个节点尽可能多的存储数据。

特点：

优点：

缺点：

B树不支持范围查询的快速查找：如果我们想要查找15和26之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
空间占用较大：如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。