概念卡片：树

一句话机制：树是分层、非线性的数据结构；二叉树到平衡二叉树、红黑树，核心是防退化（二叉查找树退化成链表）；B/B+ 树解决磁盘 IO 与范围查询，LSM 树解决随机 IO。

二叉树家族

树	定义
二叉树	每个节点最多两子
完全二叉树	除最后一层外各层满，叶子从左到右排布
满二叉树	每层节点数都达最大（总数 2^k - 1）
平衡二叉树（AVL）	左右子树高度差 ≤ 1
二叉查找树（BST）	左子树 < 根 < 右子树
红黑树	自平衡二叉查找树，5 条性质

红黑树五性质

节点非红即黑；
根节点总黑；
叶子（NIL 空节点）黑；
红节点的子节点必黑；
从根到叶每条路径的黑色节点数相同（相同黑高）。

用途：解决 BST 退化。TreeMap、TreeSet、JDK1.8 HashMap 底层都用红黑树。

B 树 / B+ 树 / B* 树

树	特点
B- 树	平衡多路查找树，节点存关键字+指针，文件系统索引用
B+ 树	叶子存全部关键字且链表相连，非叶只存索引 → 支持范围查询（range-query），数据库首选
B* 树	B+ 变体，分配新节点概率更低，空间利用率更高

B+ 树 vs B 树：

	B 树	B+ 树
关键字	n 子树 n-1 关键字	n 子树 n 关键字
叶子	不含全部信息	含全部关键字 + 链表
非叶节点	含有效信息	仅索引

LSM 树

B+ 树最大问题是大量随机 IO。LSM（Log-Structured Merge-Tree）用顺序写 + 后台合并克服，HBase 采用。

关键代码示例（二叉树插入）

BST 插入：新节点与当前节点比较，小走左、大走右，直到找到空位；相等则不重复插入。

不变量（必须成立的约束）

红黑树根必黑、红节点父子必黑、各路径黑高相同——三点共同保证平衡。
B+ 树叶子链表相连 → 支持高效范围查询，这是数据库选 B+ 的最主要原因。
平衡二叉树高度差 ≤ 1，否则退化为链表。

常见误解

以为「红黑树是严格平衡」→ 是弱平衡（黑高平衡），不如 AVL 严格但旋转少、插入删除快。
以为「B 树也能高效范围查询」→ 只有 B+ 树叶子的链表结构才能高效扫库/范围检索。
以为「LSM 树比 B+ 树快」→ LSM 牺牲读放大换写放大，适合写多读少场景。

关联