与狗狗做网站手机百度网页版入口
首先，能作为索引的数据结构有很多，例如数组、链表、二叉树
数据和索引都是存储在磁盘里的。
我们通过索引来查询数据时，先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存。
要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：
- 能在尽可能少的磁盘的 I/O 操作中完成查询工作；
- 要能高效地查询某一个记录，也要能高效地执行范围查找；
数组：
优点：用数组可以实现二分查找，时间复杂度从On降到Ologn
缺点：
- 每次查找都要不断计算中间的位置。
- 但是插入新元素的时候性能太低。（元素之后的所有元素后移一位）
二叉搜索树：
优点：（解决了数组的2个缺点）
- 每次查找只需要作比较即可
- 插入新元素时，可以任意位置插入，不需要将之后元素所有后移一位。
缺点：
- 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)
- 每访问一次节点，都要与磁盘进行一次IO操作。而树的高度就时访问节点的次数，二叉树的高度太容易高了，所以增加了IO。
自平衡二叉树：
优点：
- 解决了二叉查找树就会退化成了一条链表的问题
缺点：
- 高度问题依旧存在
需要解决高度问题，首先想到将二叉树变为M叉树，由此想到了B树
B树：
优点：
- 解决了高度问题
缺点：
- 但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。
-
而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。
- 如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。
B+树：
优点：
- B+树的非叶子节点可以存放更多的索引，在数据量相同的情况下，B+树会比B树的高度更低。
- B+ 树有许多冗余节点，而B树没有，这就使得B+树的插入和删除效率更高
- B+ 树所有叶子节点间还有一个链表进行连接，可以据此进行范围的查询，不用像B树一样只能遍历查询
