MySQL为什么不用数组、哈希表、二叉树等数据结构作为索引呢

https://blog.csdn.net/qq_34436819/article/details/105731324
我们经常所说的数据库优化，大部分优化的就是查询相关的操作。因此一个数据库选择何种数据结构作为索引，主要考虑因素就是这种数据结构对增删改查操作的效率如何，尤其是查询操作（通常查询操作包括等值查询、范围查询等）。

数组
数组对查询、删除、更新操作的效率非常高，选数组作为 MySQL 索引的数据结构看起来似乎不错。然而我们忽略了还有插入操作，如果我们要往数组中间插入一个数据，我们需要将数组中要插入的目标位置后的所有元素先往后挪动一个位置，然后才能插入新的数据，也就是涉及到了数组的复制操作，要插入的数据越靠前，那么我们需要复制的数据就越多，这个不仅需要额外开辟内存，复制数据消耗的时间也很长。

哈希表
哈希表对于删除、查找、更新、插入操作，都是先根据 key 计算出一个值，就能定位到数据的目标位置了，时间复杂度都是 O(1)，速度特别快。但是我们在使用 MySQL 时，经常会遇到查找某个范围内的数据，例如 between...and、>=、<=等范围查找操作。
因为哈希表的所有 key 都会经过哈希函数计算，然后再存放数据，本来可能有序的 key，但经过哈希函数计算出来的值就不是有序的了，
如果要在哈希表中进行范围查找，就只能对整个哈希表进行遍历了

二叉树
当我们在不停地动态地往树中插入数据、删除数据时，在极端情况下，二叉搜索树可能退化成链表，它的查找时间复杂度就变成了 O(n)，性能不够稳定。

平衡树，它的查找、删除、插入、更新的复杂度均为 O(logn)。它的中序遍历，数据是有序的，因此也适合范围查找。但是它的缺点是，为了维护平衡，它的旋转操作过于复杂。

这是因为无论是二叉搜索树，还是 AVL 树，亦或是红黑树，它们都是二叉树的一种，特点都是每个结点最多只有两个子结点，如果存储大量数据的话，那么树的高度会非常高。而 MySQL 存储的数据最终是要落地到磁盘的，MySQL 应用程序读取数据时，需要将数据从磁盘先加载到内存后才能继续操作，所以这中间会发生磁盘 IO，而如果树太高，每遍历一层结点时，就需要从磁盘读取一次数据，也就是发生一次 IO，如果数据在树高为 20 的地方，那查找一次数据就得发生 20 次 IO，这对应用程序简直就是灾难性的，耗时太长了。因此二叉树在 MySQL 这种需要存储大量数据的场景下，是不适合当做索引的数据结构的，因为树太高，操作数据时会发生多次磁盘 IO，性能太差。