B树索引的节点结构与查询效率

B树（阶为M）用”变宽降高”的思路提升查询效率：每个非叶子节点最多可以 容纳M−1个关键字、对应M个子节点指针，节点关键字按顺序排列，每个 指针指向的子树里所有关键字都落在该指针左右两个相邻关键字之间—— 这个排列规则让查询过程变成”在当前节点内二分查找定位到该往哪个指针 走，再进入下一层重复此过程”，而不需要像二叉树那样逐层只能对比一次。 “多路”（每节点能放多个关键字、指向多个子节点）换来的直接好处是树的 高度大幅降低——阶M越大，同样数据量下树的层数越少，磁盘I/O次数 （通常与树高成正比）也越少，这正是B树被设计成”胖而矮”而非”瘦而高”的 原因：磁盘I/O的成本远高于内存内比较的成本，用节点内的多次内存比较 换取更少的磁盘访问次数是划算的交易。”平衡”要求所有叶子节点必须位于 同一层，插入或删除关键字导致某条路径变短变长时，必须做节点分裂/合并 等调整操作以恢复平衡——这保证了从根到任意叶子的查询路径长度始终 一致，不会出现某些查询快、某些查询慢的不确定性。B树索引可以和数据 存储在同一文件（此时叶子节点直接存数据）或分开存储（叶子节点存指向 数据的指针），查询的时间复杂度约为O(log_M N)，其中M越大意味着树越 矮，实践中M的选择要综合考虑磁盘块大小和单条记录大小。

结构图：

flowchart TD
    A["根节点: 1~M-1个关键字<br/>1~M个子节点指针"] --> B["非叶子节点: ⌈M/2⌉-1~M-1个关键字"]
    A --> C["非叶子节点: ⌈M/2⌉-1~M-1个关键字"]
    B --> D[叶子节点<br/>所有叶子位于同一层]
    B --> E[叶子节点]
    C --> F[叶子节点]
    C --> G[叶子节点]