数据结构基础
各种数据结构的高楼大厦都需要数组和链表作地基。B+ 树、跳表、红黑树的平均时间复杂度都是 O(log n)，但不同场景下的选择依据各异。
二叉搜索树与平衡二叉树
二叉搜索树：满足一个节点最多只有两个子节点，左子树的数值小于根节点，右子树的数值大于根节点。
平衡二叉树：为了解决退化回链表的问题，要求任何节点的两个子树高度最大差为 1。若因增删导致失衡，需通过旋转恢复平衡。
MySQL 为什么使用 B+ 树
核心原因是对磁盘 I/O 的极致优化。
B 树与 B+ 树
B 树是为磁盘等外存储设备设计的平衡查找树。B 树中的每一个节点对应磁盘上的一块（Page）。
B+ 树是在 B 树基础上的优化，非叶子节点只存储键值信息，扫描相同磁盘情况下能获取更多键值。其叶子节点之间采用链式环结构。
选型理由
- 降低树高（减少 I/O）：磁盘读写速度远低于 CPU，必须减少磁盘访问次数。B+ 树的非叶子节点不存数据只存索引，使得单页能容纳更多索引，极大提升了分叉率 (Fan-out)，让树变得极度'矮胖'（通常 3 层就能存 2000w 数据）。
- 极致的范围查询：数据库常涉及范围查询。B+ 树的叶子节点由双向链表串联，找到起点后只需顺序扫描，避免了随机 I/O，大幅提升了扫描效率。
相比之下，红黑树太高（I/O 多），普通 B 树范围查询不便且非叶子节点占用内存多，所以 B+ 树是 MySQL 的不二之选。
为什么 Redis 选了跳表
跳表简单，易于理解，在一维链表上增加几个跳跃项来减少遍历查找的时间。
优势
- 实现简单：代码逻辑清晰。
- 区间查找快：O(log n) 定位区间起点，然后在原始链表中顺序往后遍历。
- 并发环境优势：红黑树插入删除可能涉及整棵树的重平衡，而跳表操作更局部，需要锁住的节点更少。
红黑树 VS 跳表
- 范围查找效率：跳表作为有序链表，对于频繁改动的数据更合适；红黑树复杂。
- 指针消耗：红黑树消耗的指针远比跳表高。
- 并发简单：Redis 是单线程内存数据库，红黑树插入可能触发整棵树旋转，牵一发而动全身；跳表只是局部修改前后节点指针。
- 维护成本：跳表代码不复杂，逻辑简单。
为什么不用 B+ 树
- CPU 消耗：B+ 树为了磁盘设计，有复杂的页分裂/合并逻辑。在内存中这些操作变成纯 CPU 累赘。
- 内存碎片：B+ 树按 Page 申请内存，存在内部碎片；跳表按需分配，无浪费。
- 代码难度：工业级 B+ 树代码量可能是跳表的 10 倍以上，Redis 作者倾向于简单、不易出 Bug 的方案。
为什么 JDK 1.8 哈希表中选择红黑树
在 Java HashMap 的使用场景（纯内存、防碰撞）下，红黑树是最佳选择。
什么是红黑树
红黑树是一种自平衡的二叉搜索树，每个节点额外存储 color 字段，确保树在插入和删除时保持相对平衡。
选型理由
- 空间利用率：B+ 树非叶子节点不存数据，这对磁盘是好事，但在内存里叫'浪费'。红黑树每个节点都存数据，在 JVM Heap 中比 B+ 树更紧凑。
- Java 对象模型：跳表节点不定长，在 C 语言里可用 malloc 动态分配，但在 Java 里对象模型固定。实现跳表需定义 Node 类包含数组或 List，这会多出数组对象头开销。红黑树结构固定（Left/Right/Parent），对 Java 内存分配器友好。
- ：HashMap 仅在链表太长（>8）时转为红黑树，目的是防止 Hash DoS 攻击。此时不需要范围查询，追求确定性。红黑树保证最坏情况也 O(log n)，而跳表靠概率平衡。
