用页式 B-tree 组织表与索引
SQLite 将表和索引组织成数据库页上的 B-tree，用一个节点容纳多个键，支持有序定位与范围遍历。
相关概念
工程问题#
数据超过内存后，逐条扫描或沿二叉树频繁访问不同页，会放大查询的存储访问成本。
实际实现#
内部页通过分隔键选择子页；页内利用有序 cell 指针定位键。普通 rowid 表的记录保存在叶页，索引采用另一种 B-tree 格式。
处理流程#
- 从表或索引的根页开始定位。
- 在当前页比较键并选择子页。
- 重复下降直到找到目标或插入位置。
- 插入后按需要平衡页面并处理溢出内容。
源码片段#
固定版本 · 原文摘录src/btree.cversion-3.46.0 · L5803–L5824
5803 if( nCellKey<intKey ){5804 lwr = idx+1;5805 if( lwr>upr ){ c = -1; break; }5806 }else if( nCellKey>intKey ){5807 upr = idx-1;5808 if( lwr>upr ){ c = +1; break; }5809 }else{5810 assert( nCellKey==intKey );5811 pCur->ix = (u16)idx;5812 if( !pPage->leaf ){5813 lwr = idx;5814 goto moveto_table_next_layer;5815 }else{5816 pCur->curFlags |= BTCF_ValidNKey;5817 pCur->info.nKey = nCellKey;5818 pCur->info.nSize = 0;5819 *pRes = 0;5820 return SQLITE_OK;5821 }5822 }5823 assert( lwr+upr>=0 );5824 idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2; */sqlite3BtreeTableMoveto
页内比较 rowid 键并缩小二分边界；命中内部页分隔键仍需下降，命中叶页才定位到记录。该分支体现 table B-tree 的键和记录布局；index B-tree 使用不同定位函数。
src/btree.cversion-3.46.0 · L5835–L5843
5835moveto_table_next_layer:5836 if( lwr>=pPage->nCell ){5837 chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);5838 }else{5839 chldPg = get4byte(findCell(pPage, lwr));5840 }5841 pCur->ix = (u16)lwr;5842 rc = moveToChild(pCur, chldPg);5843 if( rc ) break;sqlite3BtreeTableMoveto · moveto_table_next_layer
承接前一段的 goto：按 lwr 选择 cell 中的左子页指针，越过所有 cell 时选择页面头中的最右子页；随后调用 moveToChild 进入下一层。内部页命中分隔键时，前一段已经把 lwr 设为对应 cell 的下标。
两段摘录分别展示页内键比较与子页选择；中间省略了叶页未命中时的返回处理。第一段命中内部页分隔键后，通过 goto 转入第二段，再下降到对应子页。
收益与取舍#
工程分析带来的收益
- 较高扇出减少树高和跨页访问。
- 同一有序结构支持点查与范围遍历。
付出的代价
- 页分裂和平衡增加写入维护成本。
- 大记录可能使用额外的溢出页。
可比较的选择
哈希索引适合等值定位，但不能直接提供键序范围遍历。
版本与适用范围#
代码基线 3.46.0。WITHOUT ROWID 表使用索引 B-tree；索引内部页也可存键记录，不应把 SQLite 的两种树统称为标准 B+ tree。