第 299 题：实现数据库的B+树索引，范围查询与并发控制。
题目
实现数据库的B+树索引，范围查询与并发控制。
完整讲解
一、B+ 树与索引
- B+ 树：多路平衡搜索树，所有键在叶节点有序排列，且叶节点串成链表；非叶节点仅作索引（key 与子指针）。适合范围查询与磁盘：扇出大、高度低、顺序扫描叶链即可做 range query。
- 数据库索引：以 (key → 记录指针或主键) 建 B+ 树；按 key 查、范围查、排序都高效。
二、范围查询
- 点查：从根按 key 比较下行至叶，在叶中二分或扫描得 key 对应记录。
- 范围查询：在叶中找到起始 key 所在叶节点，沿叶链表顺序扫描直至结束 key；只需一次根到叶的下降 + 顺序 IO，适合「WHERE key BETWEEN a AND b」。
- 实现：节点内 key 有序；叶节点存 (key, value) 或 (key, record_id)；叶链指针维护顺序。
三、并发控制
- 读多写少：读不阻塞读；写（插入/删除/分裂/合并）需保证不破坏结构一致性。常用锁或多版本。
- ** latch（页锁）：访问节点前加 latch，可读锁（共享）或写锁（互斥）；父节点与子节点的加锁顺序一致（如从上到下、先父后子），避免死锁。Crabbing**：向下遍历时先锁子再可释放父（或保留到安全点）。
- 分裂与合并：插入导致溢出则分裂节点，新节点插入父；删除导致 underflow 可合并或借兄弟。分裂时需短暂独占父与子；可设「安全」节点（插入不分裂、删除不合并）提前释放祖先锁。
- 简单实现：每节点一把锁；搜索时读锁、修改时写锁；分裂/合并时锁路径上相关节点。可再引入意向锁或 B-link 树减少锁范围。
面试要点
- 能说清 B+ 树结构（叶节点有序+链表、非叶索引）与范围查询如何做（根到叶+顺扫叶链）。
- 能说明并发控制：latch、读锁/写锁、分裂合并时的锁顺序与 Crabbing；能简述安全节点与提前释放。
记忆要点
- B+ 树：多路平衡、叶有序+链表；范围查询=根到叶+顺扫叶链。
- 并发：节点 latch、读/写锁、分裂合并锁路径；Crabbing 或安全节点提前释放父锁。