mysql

索引的底层数据结构了解过吗？

❒ 二叉树

✔ 正常情况下，二叉树避免全表扫描的问题，减少查询次数。
✔ 但是对单边增长的情况并不友好,单边增长的倾斜问题，变相为链表，查找效率低，与全表扫描差别不大。
✔ 平衡二叉树（AVL）树平衡条件必须满足所有节点的左右子树高度差不超过1。只要不满足条件，就要通过旋转来保持平衡，因为旋转非常耗时。所以平衡二叉树（AVL）适合用于插入与删除次数比较少，但查找多的情况。

❒ 红黑树

✔ 在平衡二叉查找树的基础上增加了着色和相关的性质，使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn)。所以红黑树适用于搜索，插入，删除操作较多的情况。
✔ 大数据量情况下，高度不可控。需要对红黑树进行优化，也就是控制树的高度

❒ B-Tree

✔ 叶节点具有相同的深度，叶节点的指针为空
✔ 所有索引元素不重复
✔ 节点中的数据索引从左到右递增排列
✔ 每个叶节点可以放很多个数据（多阶），这就比刚才的红黑树优化了一点点

❒ B+Tree

✔ 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
✔ 叶子节点存储数据
✔ 叶子节点之间用指针连接，提高区间访问的性能（也就是说在每个叶子之间有一个指针，这个是B-Tree所没有的。有了这个指针可以范围查询。）

❒ MySQL的InnoDB引擎采用的B+树的数据结构来存储索引

✔ 阶数更多，路径更短
✔ 磁盘读写代价B+树更低，非叶子节点只存储指针，叶子节点存储数据
✔ B+树便于扫库和区间查询，叶子节点是一个双向链表