B+树节点结构与数据库索引应用

可视化演示

展示B+树的内部节点扇出、叶子节点链表结构与范围查询过程，揭示数据库索引的高效搜索原理。

节点家族三成员

图书馆的“找书系统”分三级：入口的总目录卡、每层的引导牌、还有真正放书的书架。小艾有一个严格规定——引导牌上绝不堆书，书架上绝不兼职指路。各司其职，整个找书流程才不会乱。

B+树的节点也分三类：根节点、内部节点（统称非叶子节点）和叶子节点。根节点是树的唯一入口，内部节点是层层分流的“引导牌”，而所有真正的数据记录，只存放在叶子节点中。这与普通 B 树“每个节点都可以存数据”的朴素设计截然不同，是 B+树性能优势的起点。

一个内部节点里放着若干“键”和若干“指针”：键是分隔值，指针指向覆盖对应键范围的子节点。规律很清晰——n 个键把一维区间切成 n+1 段，所以指针数总是比键数多 1。查询从根出发，每层根据目标值与键的比较选一条指针下降，直到叶子。

$$\displaystyle N_{ptr} = N_{key} + 1$$

1. N_key（键数）：节点中用于分隔子区间而存放的键的个数，相当于引导牌上的书号边界。

$$\displaystyle N_{key}$$

2. N_ptr（指针数）：指向下一层子节点的指针个数，相当于引导牌上的“箭头”数量。

$$\displaystyle N_{ptr}$$

3. +1 的来源：n 个键把范围切成 n+1 段，每段必须有一个指针，所以指针数恒为键数加一。

$$\displaystyle N_{ptr} = N_{key} + 1$$

小艾很清楚：引导牌上写 3 个书号区间，就得画 4 个箭头；书架永远不会出现在引导牌那一层。这份“分工洁癖”正是 B+树维持高效的根本。

内部节点与扇出

引导牌尺寸固定，一行写一个“范围 → 箭头”。小艾发现，决定找书快慢的关键变量是：一张引导牌上能写多少行。写得多，读者被疏散到更多子区域，平均要多走的路就少——这个“一块牌能带几条路”的能力，在 B+树里叫扇出（fanout）。

在 B+树中，内部节点的容量由所在页（page）大小决定，每一行配置是一个“键 + 指针”对。于是扇出约等于页大小除以单个键与指针的字节数总和。键越短、指针越紧凑，扇出越大，树就越“矮胖”。

假设页大小 P，平均键长 K，指针长 T，则扇出：

$$\displaystyle m \approx \left\lfloor \frac{P_{page}}{K_{key} + T_{ptr}} \right\rfloor$$

InnoDB 默认 16KB 页，配上 8 字节的 bigint 主键和 6~8 字节的指针，扇出轻松上千。这意味着三层树就能覆盖百万级节点，四层就能支撑上亿行数据的索引。

1. P_page（页大小）：节点可用的存储空间，也就是一次磁盘 I/O 能读入的数据量。

$$\displaystyle P_{page}$$

2. K_key + T_ptr（键指针组合）：内部节点中一行“键 + 指针”占用的平均字节数。

$$\displaystyle K_{key} + T_{ptr}$$

3. 相除取整：总字节数除以单行字节数得到可容纳行数，向下取整保证不越界。

$$\displaystyle \left\lfloor \frac{P_{page}}{K_{key} + T_{ptr}} \right\rfloor$$

于是小艾规定：引导牌的标签一律用最简短的编号（“B~M“而不是”文学类 B 区到文学类 M 区”），一行塞下的信息越多，读者少跑两层楼。这不是经验玄学，而是有公式可算的工程权衡。

叶子链表与查询

读者想借“B 到 M 区所有书”。小艾的聪明办法是：书架之间修一条前后贯通的通道，找到起点书架后，顺着通道一本本往后取，全程不用回总目录。在 B+树里，这条通道就是叶子节点之间的双向链表。

叶子节点按键升序存放完整记录，且每个叶子都有 prev / next 指针，串成一条有序的“叶子链表”。这个设计的直接收益是范围查询：先沿树找到左端点所在的叶子（需要 h 次 I/O），再沿链表顺序扫描即可，完全不必逐层回溯。

设树高为 h，每个叶子页平均容纳 L 条记录，范围查询要取 r 条记录，则 I/O 次数约为：

$$\displaystyle T_{range} = h + \left\lceil \frac{r}{L} \right\rceil$$

1. h（树高定位）：从根到左端点叶子的路径长度，是范围查询的固定开销。

$$\displaystyle h$$

2. r / L（扫描叶页数）：结果数量除以每页记录数，就是需要顺序读取的叶子页数。

$$\displaystyle \frac{r}{L}$$

3. 向上取整：即使某页只读一条记录也要一次 I/O，所以按页数向上取整。

$$\displaystyle \left\lceil \frac{r}{L} \right\rceil$$

小艾总说：“书架间的通道比天花板上的航拍图重要。” 点查靠树找对书架，批量取书靠通道顺藤摸瓜——这正是数据库 WHERE key BETWEEN ... 能秒回的原因。

盘页对齐设计

图书馆的搬运小车是定制的：一次刚好能装一格书。如果书架格子比小车大，一趟要跑两趟；比小车小，装不满浪费。所以小艾把每一格都按小车容量设计，不多不少。

磁盘读写以“页”为最小单位，数据库一次 I/O 至少读入一整页。B+树的每个节点大小刻意与磁盘页对齐：一个节点恰好占一页（InnoDB 默认 16KB、PostgreSQL 默认 8KB）。这样一次 I/O 就能读入一个完整节点，不浪费任何字节。

点查询沿树下行 h 层，每层访问一个节点就是一次页 I/O，因此：

$$\displaystyle T_{point} = h \times T_{io}$$

其中 T_io 是单次磁盘 I/O 的耗时（毫秒级）。树高 3~4 层的 B+树，点查询固定只要 3~4 次 I/O，与数据总量几乎无关——这正是索引能“扛住亿级数据”的底气。

1. h（层数）：点查询从根到叶子，每层只访问一个节点。

$$\displaystyle h$$

2. T_io（单次 I/O 耗时）：读一个节点对应一次磁盘页 I/O，是查询的主要成本。

$$\displaystyle T_{io}$$

3. 相乘得总开销：总耗时约等于层数乘以单次 I/O 时间，所以减少树高就是缩短延迟。

$$\displaystyle T_{point} = h \times T_{io}$$

小艾把书架、小车、通道都按同一个“格”来设计——对齐的代价是前期测量，收益是每次搬书都一步到位。数据库里页大小与节点大小的对齐，同理。

分裂合并平衡

某天“推理小说”书架满了，新书没处放。小艾的做法是：把书架从中间拆成两个，中间那本书“升级”到引导牌上当新路标，两边各放一半。过几天隔壁书架太空了，她又把两架合并。这样书架永远不溢出，也永远不浪费。

B+树插入时先定位叶子，若节点已满（键数达到上限 m），则分裂为两个节点，并把中间键提升到父节点继续充当分界。若父节点也因此变满，则继续向上分裂，直到根——根分裂时树整体增高一层。删除时若节点过空，则向兄弟借键或合并，必要时向下级联调整。

对满节点插入第 m+1 个键时，中间位置满足：

$$\displaystyle j = \left\lfloor \frac{m+1}{2} \right\rfloor$$

左侧保留前 j 个键，第 j 个键作为“中间键”提升到父节点，剩余键交给右侧新节点。由于数据只存在叶子且提升键随时上移，B+树始终满足“所有叶子在同一层”，即绝对平衡。

1. m+1（临时候数）：满节点插入新键后，节点里暂时有 m+1 个键。

$$\displaystyle m+1$$

2. 取半下整（左侧键数）：算出左侧节点应保留的键数 j，保证分裂后两边大致均衡。

$$\displaystyle \left\lfloor \frac{m+1}{2} \right\rfloor$$

3. 中间键提升（新分界）：第 j 个键上移到父节点，作为左右两个新区域的边界。

$$\displaystyle j = \left\lfloor \frac{m+1}{2} \right\rfloor$$

书架的拆与并看似只是体力活，但小艾每次都要同步更新引导牌——对应数据库在分裂合并时对父节点的级联修改。平衡不是天生的，而是“拆了必须改路标”这套纪律换来的。

数据库实现差异

城北图书馆 A 馆规定：书必须按索书号排架，找到书架就是找到书，这叫“书跟号走”。城南借书处 B 馆则把书随意放，但每本都贴一张“位置纸条”：第几排第几格。两家都能快速找书，但内部分工完全不同。

MySQL InnoDB 与 PostgreSQL 正是这两派。InnoDB 使用聚簇索引：主键索引的叶子节点直接存放整行数据，表数据“跟着主键走”；二级索引的叶子则存主键值，查询要先走二级索引，再回聚簇索引拿整行。PostgreSQL 采用堆表：行数据放在堆（heap）中，索引叶子存放的是行的物理位置 TID（页号 + 偏移量），所有索引（含主键）都是非聚簇的。

在 InnoDB 中，二级索引等值查询通常要访问两棵 B+树：

$$\displaystyle T_{secondary} = h_{sec} + h_{clu}$$

h_sec 是二级索引树高，h_clu 是聚簇索引树高。此外两者页大小不同（16KB 与 8KB），导致扇出和树高存在差异。理解这些差异，才能解释“为什么同样的 SQL 在两个库里表现不同”。

1. h_sec（二级索引树高）：先用二级索引这棵 B+树把目标主键找出来。

$$\displaystyle h_{sec}$$

2. h_clu（聚簇索引树高）：再拿主键回聚簇索引这棵 B+树读取完整行。

$$\displaystyle h_{clu}$$

3. 相加（回表总开销）：两棵树各走一遍，所以二级索引回表查询是最坏情况。

$$\displaystyle T_{secondary} = h_{sec} + h_{clu}$$

小艾去 A 馆参观后感叹：A 馆“号到书到”少一趟路，但改索书号等于重排满馆书架，成本高；自己用“位置纸条”灵活，却总要多看一眼纸。没有绝对好坏，只有围绕主键的取舍。

索引策略与优化

小艾总结出了一套选书架铁律：书号越短，引导牌能写的行越多（扇出大），树就越矮；书号递增，新书永远加在最后一格，书架难得拆。这四条经验，换成数据库术语就是主键选择与索引设计策略。

树高与扇出、记录数的关系是指数级的：

$$\displaystyle h = \left\lceil \log_{m} N \right\rceil$$

扇出 m 越大，树高增长越慢。假设扇出 1000，树高 3 即可覆盖百万级节点；若键变成又长又宽的 varchar(200)，扇出骤降，树变高，每次查询多一层就多一次 I/O。

由此得出实用策略：其一，主键选小且有序（自增 bigint 最优），避免随机 UUID 引发大量页分裂与碎片；其二，按真实查询模式建索引，但不是越多越好——每多一个索引就多一棵 B+树，写入要同步维护，产生写放大；其三，用覆盖索引（联合索引包含所需全部列）让查询在索引页内拿齐数据，免回表。

1. N（记录数）：要索引的数据总量，对应馆藏图书总册数。

$$\displaystyle N$$

2. m（扇出）：每个内部节点平均指向的子节点个数，对应引导牌的容纳行数。

$$\displaystyle m$$

3. 以 m 为底的对数再上整：树高等于记录数按扇出取对数的上整，扇出翻倍树高减一。

$$\displaystyle h = \left\lceil \log_{m} N \right\rceil$$

小艾把四条铁律贴在工作台：号短、号涨、路牌字小稀疏、通道少而精。数据库里每一次建索引、选主键，其实都在回答同一个问题：你愿意为“读得快”付出多少“写得慢”的代价？

AI 应用场景

Python 演示

import bisect class Node:    # B+树节点: 叶子存数据, 内部节点只存键和子指针    def __init__(self, leaf=False):        self.leaf = leaf        self.keys = []            # 键, 升序排列        self.childs = []          # 内部节点的子指针        self.vals = [] if leaf else None  # 叶子节点的数据        self.next_leaf = None     # 叶子链表后继  class BPlusTree:    # 简化版 B+树: 支持 insert / search / range_query    def __init__(self, order=4):        self.order = order        # 节点最大键数        self.root = Node(leaf=True)     def _find_leaf(self, key):        n = self.root        while not n.leaf:            i = bisect.bisect_right(n.keys, key)            n = n.childs[i]        return n     def _height(self, n):        if n.leaf:            return 1        return 1 + self._height(n.childs[0])     def search(self, key):        n = self._find_leaf(key)        i = bisect.bisect_left(n.keys, key)        if i < len(n.keys) and n.keys[i] == key:            return n.vals[i]        return None     def range_query(self, lo, hi):        n = self._find_leaf(lo)        res = []        while n is not None:            for k, v in zip(n.keys, n.vals):                if k > hi:                    return res                if k >= lo:                    res.append(v)            n = n.next_leaf        return res     def insert(self, key, val):        split = self._insert(self.root, key, val)        if split is not None:            left, mid_key, right = split            root = Node()            root.keys = [mid_key]            root.childs = [left, right]            self.root = root     def _insert(self, n, key, val):        if n.leaf:            i = bisect.bisect_left(n.keys, key)            n.keys.insert(i, key)            n.vals.insert(i, val)            if len(n.keys) <= self.order:                return None            mid = len(n.keys) // 2            right = Node(leaf=True)            right.keys = n.keys[mid:]            right.vals = n.vals[mid:]            right.next_leaf = n.next_leaf            n.next_leaf = right            n.keys = n.keys[:mid]            n.vals = n.vals[:mid]            return (n, right.keys[0], right)        i = bisect.bisect_right(n.keys, key)        split = self._insert(n.childs[i], key, val)        if split is None:            return None        left, mid_key, right = split        j = bisect.bisect_left(n.keys, mid_key)        n.keys.insert(j, mid_key)        n.childs.insert(j + 1, right)        if len(n.keys) <= self.order:            return None        mid = len(n.keys) // 2        up = n.keys[mid]        right_node = Node()        right_node.keys = n.keys[mid + 1:]        right_node.childs = n.childs[mid + 1:]        n.keys = n.keys[:mid]        n.childs = n.childs[:mid + 1]        return (n, up, right_node)  if __name__ == '__main__':    tree = BPlusTree(order=4)    lib = {5: 'Little Prince', 12: 'Algorithm',           25: 'Three Body', 32: 'Deep Learning',           40: 'Statistics', 58: 'LLM Ops'}    for k, v in lib.items():        tree.insert(k, v)    print('search 25 ->', tree.search(25))    print('range [12, 40] ->', tree.range_query(12, 40))    print('height ->', tree._height(tree.root))

1. n = self.root; while not n.leaf从根出发，沿内部节点的“引导牌”逐层下降，直到进入叶子。
2. i = bisect.bisect_right(n.keys, key)在内部节点键数组中二分定位，找到第一个大于 key 的位置作为下降子树下标。
3. n.keys.insert(i, key); n.vals.insert(i, val)向叶子有序插入键值对，保持叶子内升序。
4. return (n, right.keys[0], right)叶子分裂后返回“右节点最小键”，由上层把它提升为父节点的新分界。
5. n.childs.insert(j + 1, right)父节点在正确位置挂上新子节点，保证键与指针的排列依然有序。
6. while n is not None: ... n = n.next_leaf范围查询定位起点后沿叶子链表顺序扫描，收集落在区间内的所有记录。

常见误区

面试题