【SQLite 内核】B-Tree 遍历与分裂：表 B-Tree、索引 B-Tree 与 cell 布局
内容提要
SQLite的B-Tree模块分为table b-tree（64位整数key，数据仅存叶子，近似B+Tree）和index b-tree（任意key，不存数据）。页内通过cell pointer array实现逻辑有序与物理位置解耦，插入时无需搬移已有内容。overflow阈值保证索引树最小扇出为4。查找从根页二分至叶子，分裂合并由balance()统一触发，分派至balance_deeper、balance_nonroot或balance_quick。
延伸解读
两种B-Tree的差异与误解
SQLite的B-Tree并非教科书中的经典B-Tree：table b-tree数据只在叶子，更接近B+Tree；index b-tree不存数据，是纯key结构。WITHOUT ROWID表并非简单省去隐藏列，而是整表变为index b-tree，存储范式改变。理解这些差异有助于避免设计误区。
cell pointer array的插入优势
cell pointer array将逻辑顺序与物理位置解耦，插入新cell时只需在指针数组中插入偏移，无需搬移已有cell内容，但会积累碎片，需要defragment整理。这种设计在频繁插入场景下能减少写放大，但碎片整理可能带来额外开销。
overflow阈值与性能影响
overflow阈值设计保证index b-tree最小扇出为4，避免超长key导致树退化。但溢出内容存储在独立链上，顺序读取，大字段会拖慢范围扫描。设计表结构时，应避免在索引列使用超长值，以减少溢出页I/O。
balance()触发条件与写放大
balance()不仅处理分裂，也处理合并，触发条件包括页有overflow cell或空闲空间超2/3。balance_quick针对右端追加优化，但可能造成树不平衡。实际写放大受页大小、插入模式等影响，需实验验证，本文未提供具体数据。
Q&A
SQLite中的table b-tree和index b-tree有什么区别？
Table b-tree使用64位有符号整数作为key，数据只存储在叶子节点，内部节点只存子页指针和rowid，不存payload，行为上更接近B+Tree。Index b-tree使用任意长度的key，不存储数据，key由被索引列和行key（rowid或主键）组成。
SQLite的cell pointer array是如何实现逻辑有序与物理位置解耦的？
Cell pointer array是页内的一组2字节偏移量，按key的逻辑顺序排列。插入新cell时，只需在pointer array中插入新偏移并移动后续偏移，已有cell内容不搬移，从而实现了逻辑顺序与物理位置的解耦。
SQLite的overflow阈值设计目标是什么？
Overflow阈值的设计目标是保证index b-tree的最小扇出为4，即无论key多长，内部页至少能容纳4个key，避免树退化为链表。
SQLite的balance()函数在什么条件下触发分裂或合并？
balance()在以下任一条件满足时触发：页上有overflow cell（页即将写满），或页上没有overflow cell但空闲空间超过可用空间的2/3（页太空）。它统一处理分裂和合并。
SQLite的balance_deeper、balance_nonroot和balance_quick分别用于什么场景？
balance_deeper用于根页过满时，分配新子页并将根页内容拷贝进去，使树长高一层；balance_nonroot是常规路径，重新分配当前页及最多两侧各一个兄弟页的cell；balance_quick是右端追加时的快路径，直接分配新右兄弟页，不调整其他兄弟。
WITHOUT ROWID表在存储上有什么本质变化？
WITHOUT ROWID表没有独立的table b-tree，整张表就是一棵index b-tree，key由主键列和剩余列组成，没有rowid，也没有单独的数据b-tree。这改变了存储范式，不只是省去一个隐藏列。
SQLite的查找路径是怎样的？
查找从根页开始，在cell pointer array上二分查找，根据key比较结果选择子指针，重复直到叶子页，再在叶子页二分查找命中或确定插入位置。table b-tree用整数比较，index b-tree按列和collation比较。
