B树

B树的节点容纳多个有序键，并用这些键区分若干子树的取值范围。查找时先在当前节点决定目标属于哪一段，再进入对应子树。多路分支使树可以保持较低高度，尤其适合一次读取能带回一整页数据的存储环境，让一次页面访问完成较多判断。

参考：[1]

插入会改变节点所含的键，节点过满时需要分裂，并把分隔信息传到上层；删除则可能触发重新分配或合并。具体上下限由树的定义与实现规定。这些操作共同维护高度与容量性质，避免数据按照某种顺序到达时，树逐渐退化成需要长距离逐项追踪的链。

参考：[2]

有序组织不仅适合查找某个相等键，还能定位一个范围的起点，再继续取得相邻结果。数据库索引因此可以支持比较、排序与范围检索，但是否被优化器采用，还取决于数据量、选择性和查询要求。组合索引还需要考虑各列的顺序，不能仅凭建了索引就保证每个条件都同样高效。

参考：[1]

B树家族有多种具体形式，B+树常把记录或记录引用集中在叶层，并组织叶之间的顺序联系。不同数据库的并发更新、页面分裂和恢复办法也会影响实际成本。说明一个索引时，应结合它的具体变体与存储设计，而不把所有多路平衡树的布局细节混成同一套实现。

参考：[2]