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+树

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

解决了范围查找问题

查找过程

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