MySQL索引结构演变历史
什么是索引
索引定义：索引是依靠某些数据结构和算法来组织数据，最终引导用户快速检索出所需要的数据
例如新华字典中，我们可以通过偏旁部首或者拼音快速找到我们需要查找的字；这里的偏旁部首和拼音就是索引
索引选择数据结构历史
1.有序数组
优点 ：
可以通过下标随机访问数据
缺点：
查找数据时需要将整个表数据都加载到内存中，内存压力非常大
且存储数据时需要考虑到指针移动问题，
2.链表
优点：
- 可以快速定位到上一个或者下一个节点
- 可以快速删除数据，只需改变指针的指向即可，这点比数组好
缺点：
- 无法向数组那样，通过下标随机访问数据
- 查找数据需从第一个节点开始遍历，不利于数据的查找，查找时间和无需数据类似，需要全遍历，最差时间是O(N)
3.二叉查找树
二叉树的优缺点：
- 查询数据的效率不稳定，若树左右比较平衡的时，最差情况为O(logN)，如果插入数据是有序的，退化为了链表，查询时间变成了O(N)
- 数据量大的情况下，会导致树的高度变高，如果每个节点对应磁盘的一个块来存储一条数据，需io次数大幅增加，显然用此结构来存储数据是不可取的
正常数据
image-20230710150628613异常数据
image-202307101506492354.平衡二叉树（AVL树）
平衡二叉树是一种特殊的二叉树，所以他也满足前面说到的二叉查找树的两个特性，同时还有一个特性：
它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树相对于二叉树来说，树的左右比较平衡，不会出现二叉树那样退化成链表的情况，不管怎么插入数据，最终通过一些调整，都能够保证树左右高度相差不大于1。
但是当数据量非常大时，也会和二叉树一样出现树的高度过高问题
5.B-树
image-20230710150606776由平衡二叉树变化而来，每个节点中存储多个元素，节点中多个元素通过指针关联，解决了数据量大时，树的高度过高问题；
但是无法解决范围查找问题，例如查找15,36还是需要访问7个磁盘块（1/2/7/3/8/4/9）
6.b 树
image-20230710150550907优化后 只在叶子结点中存储数据，其他节点只存储关键字，叶子结点之间通过双向指针关联
解决了范围查找问题
查找过程
先定位范围的最大值和最小值，然后子节点中依靠链表遍历范围数据
