MySQL 索引结构演变历史

MySQL 索引结构演变历史

什么是索引

索引定义：索引是依靠某些数据结构和算法来组织数据，最终引导用户快速检索出所需要的数据

例如新华字典中，我们可以通过偏旁部首或者拼音快速找到我们需要查找的字；这里的偏旁部首和拼音就是索引

索引选择数据结构历史

1.有序数组

优点 ：

可以通过下标随机访问数据

缺点：

查找数据时需要将整个表数据都加载到内存中，内存压力非常大

且存储数据时需要考虑到指针移动问题，

2.链表

优点：

1. 可以快速定位到上一个或者下一个节点

2. 可以快速删除数据，只需改变指针的指向即可，这点比数组好

缺点：

1. 无法向数组那样，通过下标随机访问数据

2. 查找数据需从第一个节点开始遍历，不利于数据的查找，查找时间和无需数据类似，需要全遍历，最差时间是 O(N)

3.二叉查找树

二叉树的优缺点：

1. 查询数据的效率不稳定，若树左右比较平衡的时，最差情况为 O(logN)，如果插入数据是有序的，退化为了链表，查询时间变成了 O(N)

2. 数据量大的情况下，会导致树的高度变高，如果每个节点对应磁盘的一个块来存储一条数据，需 io 次数大幅增加，显然用此结构来存储数据是不可取的

正常数据

异常数据

4.平衡二叉树（AVL 树）

平衡二叉树是一种特殊的二叉树，所以他也满足前面说到的二叉查找树的两个特性，同时还有一个特性：

它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树相对于二叉树来说，树的左右比较平衡，不会出现二叉树那样退化成链表的情况，不管怎么插入数据，最终通过一些调整，都能够保证树左右高度相差不大于 1。

但是当数据量非常大时，也会和二叉树一样出现树的高度过高问题

5.B-树

由平衡二叉树变化而来，每个节点中存储多个元素，节点中多个元素通过指针关联，解决了数据量大时，树的高度过高问题；

但是无法解决范围查找问题，例如查找[15,36]还是需要访问 7 个磁盘块（1/2/7/3/8/4/9）

6.b+树

优化后 只在叶子结点中存储数据，其他节点只存储关键字，叶子结点之间通过双向指针关联

解决了范围查找问题

查找过程

先定位范围的最大值和最小值，然后子节点中依靠链表遍历范围数据