红黑树、B树、B+树

前言

通过问答的方式来了解一下树的演变。

一、抛砖

问：mysql 存储索引用的什么数据结构
答：B+树问：B+树的查询复杂度是多少？
答：和树的高度有关，一般是O(logₘN),M为树的阶数，即每个节点包含的子节点数问：hash的查询复杂度呢？
答：O(1)问：那为什么不用hash，而用B+树呢
答：请看。。。

二、引玉

问：关于树都有哪些知识点呢？
答：前中后序遍历、二叉树、平衡二叉树、B树、B+树、红黑树等等。问：二叉树的排序特点知道吗
答：左节点比根节点小，右节点比根节点大；且左右子树都是二叉排序树。问：但是极端情况下，会退化成链表（比如节点是倒序插入）
答：了解，所以要用平衡树，插入时调整这棵树，尽可能的保持节点均匀分布。问：没错，红黑树其实也是平衡树的一种，它的各种复杂规则都是为了保持平衡。但是为什么保持平衡呢？
答：因为树的查询性能取决于树的高度，保持平衡是为了降低树的高度。问：没错，Java中用一个数据结构就是采用的红黑树，你知道吗
答：TreeSet、TreeMap、以及HashMap(数组长度大于64且链表长度大于8)问：B树了解多少呢？
答：1、多路平衡查找树，所有叶子节点位于同一层（深度相同），且通过插入、删除时的 “分裂”“合并” 操作维持平衡性，确保查询效率稳定在 O (logₘn)（m 为阶数）。2、每个节点可以包含多个关键字和多个子节点，且子节点数受阶数（m）限制问：那为什么要设计成多路呢？
答：是为了降低树的高度，提高查询效率问：那是否可以设计成无限路？
答：可以吧，但是会退化成有序数组问：会有问题，你想一下B树的使用场景呢？
答：一般用在稳健系统的索引上。问：那么为什么文件系统不用有序数组或者红黑树呢？
答：文件系统和数据库索引都是在硬盘上的，如果数据量大的话不一定能一次性加载到内存中。问：没毛病，那一棵树无法完全加载的话，你该怎么查找呢
答：可以一个节点一个节点的查找，层级递进，这时候多路的好处就体现出来了。问：没错，如果在内存中，红黑树比B树效率更好，但是涉及到磁盘，B树就更好了。下面你能讲讲B+树吗？
答：B+树在B树的基础上做了改造，数据都存在叶子结点，且叶子结点之间用指针链接成链表。问：那为什么要这么设计呢？
1、这种设计让非叶子节点可以容纳更多关键字（因为不需要预留空间存储数据），从而降低树的高度，减少 IO 次数，提升查询效率
2、当数据更新时，只需修改叶子节点，无需同步非叶子节点，减少了一致性维护的成本
3、叶子节点用指针链接成链表：高效支持范围查询
4、适配外存的 “块读取” 特性，外存的IO操作以 “块” 为单位（如4KB/块），一次 IO 可读取整个叶子节点的数据。