MySQL索引底层数据结构与算法

什么是索引

索引是帮助MySQL高效获取数据的排好序的数据结构。

索引数据结构

推荐大家一个数据结构的网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

为什么不是二叉树

当我们利用索引查询的时候，不可能把整个索引全部加载到内存，只能逐一加载每个磁盘页，磁盘页对应索引树的节点。
那么Mysql衡量查询效率的标准就是磁盘IO次数。
为了减少磁盘IO的次数，就需要尽量降低树的高度。
而且极端情况下N条数据需要查询N次才可以找到该条数据（如图查找6，需要查找六次），因此二叉树不适合作为MySQL的索引。

为什么不是红黑树

可以看到虽然红黑树对数据进行了平衡处理，不会导致单边增长。但是当数据量很大的时候，红黑树的深度会很深，这样一来查询数据还是会很耗时。

为什么不是B树

从B树结构可以看到，扩大了横向深度，减少了纵向深度，从而提高查询速度而不影响存储数据容量。
但是java拿取数据的过程是这样的：java程序-> cpu -> 内存 -> 硬盘
而内存与硬盘的交互是有大小限制的，Innodb的默认大小为16K

show global variables like 'innodb_page_size';

而B树在所有节点都存储了数据，那么一次io查询出来的数据量就不会很多，查询效率也相对不高。

为什么是B+树

B+Tree通过把data不放在非叶子节点来增加度（小节点），从而一次IO可以查询出更多的索引数据，减少查询次数。
并且，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找，而不再从上面节点往下一个个找。
可以看出B+树即减少了查询次数，又提供了很好的范围查找，对比二叉树、红黑树、B树都更适合作为MySQL的索引数据结构。

为什么是HASH

MySQL也支持hash数据结构的索引。因为在=查询的时候，大部分情况下效率要优于B+树。

MyISAM索引实现

MyISAM索引文件和数据文件是分离的，数据.MYD+结构.frm+索引.MYI三个文件。
非主键索引和主键索引叶子节点都存储的文件指针地址。

InnoDB索引实现

主键索引也叫聚簇索引，叶子节点存储了完整数据，非聚簇索引叶子节点存储了主键id。

为什么非主键索引结构叶子节点存储的是主键值？
1.节省空间
指向主键的节点，不用再存储一份相同的数据。但是利用非主键查询时可能会有回表（通过叶子节点的主键值，重新查询完整数据。只查询索引列的值则不用回表）的操作。
2.一致性
修改数据时，只需要修改主键的data，如果非主键索引也存储，那么就需要修改多份数据，所以非主键存储主键索引就可以保持数据的一致性。