第 4.1 章树索引

Search Trees, Balance, and External-Memory Indexing

引入

当数据量变大以后，最大的问题是怎样尽快找到我们想要的数据。

共同目标：让查询沿着一条短而有方向的路径前进，而不是扫描全部数据。

索引树需要特殊设计

同样一组关键字，只满足“左小右大”还不够；树形状会直接决定搜索代价。

二叉搜索树（Binary Search Tree，BST）的操作都是 \(O(h)\)。如果结构退化，\(h\) 可以从 \(O(\log n)\) 变成 \(O(n)\)。

本章的核心就是：怎样增加结构约束，使搜索路径在目标工作负载下保持足够短。

学习目标

掌握二叉搜索树的定义、查找、插入、删除
理解二叉搜索树高度对复杂度的决定性影响
掌握带顺序统计（order statistics）的二叉搜索树（Indexed BST）的 leftSize 思想
掌握 AVL 树平衡因子（balance factor）、旋转（rotation）和高度界
理解多路搜索树（m-way search tree）的区间划分
正确定义 B 树（B-tree）的阶、结点容量、叶层一致性
区分 B 树与 B+ 树（B+ tree）的数据存放方式和范围查询（range query）能力

本章路线图

特殊树
搜索与平衡

二叉搜索树
有序约束 · 查找 / 插入 / 删除顺序统计
子树大小 · 第 k 小 AVL 树
旋转恢复平衡 · 保证树高多路搜索树
一个结点容纳多个关键字 B 树
降低树高 · 面向外存访问 B+ 树
叶层有序 · 范围查询与索引

二叉搜索树

二叉搜索树定义

二叉搜索树可以为空。

非空二叉搜索树满足：

每个结点有唯一关键字
左子树所有关键字小于根关键字
右子树所有关键字大于根关键字
左右子树也都是二叉搜索树

二叉搜索树示例

中序遍历二叉搜索树会得到递增序列。

查找操作

二叉搜索树：查找代码与复杂度

static <Key extends Comparable<? super Key>> Node<Key> find(Node<Key> root, Key key) {
  while (root != null) {
    int comparison = key.compareTo(root.key);
    if (comparison < 0) {
      root = root.left;
    } else if (comparison > 0) {
      root = root.right;
    } else {
      return root;
    }
  }
  return null;
}

find(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。

每轮只比较目标关键字与当前根关键字；二叉搜索树的全局有序性让这一次比较足以决定下一步搜索方向。

较小只可能在左子树，较大只可能在右子树，相等立即命中；每一步都会整棵丢弃不可能的一侧，因此只访问一条根到结点的路径。

若路径走到 null 仍未命中，候选集合已经为空；查找失败。总成本是 O(h)，由树高而不是结点总数直接决定。

`findMin` 与 `findMax`

最小值和最大值不需要“搜索整个二叉搜索树”。因为二叉搜索树的顺序关系已经把方向写进结构里：最小值只可能沿左孩子链出现，最大值只可能沿右孩子链出现。

`findMin` / `findMax` 代码

沿一个指针走到底：

static <Key extends Comparable<? super Key>> Node<Key> findMin(Node<Key> root) {
  if (root == null) {
    return null;
  }
  while (root.left != null) {
    root = root.left;
  }
  return root;
}

static <Key extends Comparable<? super Key>> Node<Key> findMax(Node<Key> root) {
  if (root == null) {
    return null;
  }
  while (root.right != null) {
    root = root.right;
  }
  return root;
}

findMin(…) 沿有序树的最左路径寻找最小关键字，不需要扫描其他分支。

二叉搜索树中更小的关键字只能出现在左边；因此非空树的最小值沿左孩子一直走到尽头即可得到，完全不需要检查右子树。

findMax(…) 返回整个序列的最大元素；扫描过程中只需维护“已看前缀的最大值”这一不变量。

最大值完全对称：沿右孩子走到底。两个操作都只访问一条根到极值节点的路径，时间为 O(h)。

二叉搜索树插入

插入先做一次和查找完全相同的比较路径。真正不同的只有最后一步：当应该继续前进的孩子是 null 时，就在那个位置创建新叶结点。

下面把 61 插入到当前二叉搜索树。注意整个过程中原有结点都不需要搬动。

二叉搜索树插入代码

递归代码中的 root == null 对应搜索路径最终到达的空孩子位置。

private static <Key extends Comparable<? super Key>> int size(Node<Key> node) {
  return node == null ? 0 : node.size;
}

private static <Key extends Comparable<? super Key>> int height(Node<Key> node) {
  return node == null ? -1 : node.height;
}

private static <Key extends Comparable<? super Key>> void refresh(Node<Key> node) {
  node.height = 1 + Math.max(height(node.left), height(node.right));
  node.size = 1 + size(node.left) + size(node.right);
}

static <Key extends Comparable<? super Key>> Node<Key> insert(Node<Key> root, Key key) {
  if (root == null) {
    return new Node<>(key);
  }
  int comparison = key.compareTo(root.key);
  if (comparison < 0) {
    root.left = insert(root.left, key);
  } else if (comparison > 0) {
    root.right = insert(root.right, key);
  } else {
    return root;
  }
  refresh(root);
  return root;
}

size(…) 只报告当前逻辑规模，不应触发结构遍历或修改。

size 把空子树视为 0 个结点，非空时直接读缓存；排名查询因此不需要重新数整棵子树。

height(…) 返回子树高度；空树给出基值，非空结点取两个孩子高度的较大者再加 1。

height 把空子树视为 -1，让叶子高度自然得到 0；AVL 等高度维护可直接复用这个约定。

refresh(…) 根据孩子状态重算结点的派生信息，使高度/规模字段重新与子树一致。

refresh 只根据两个孩子重新计算当前结点的高度和规模；结构一旦变化，缓存必须立即跟上真实子树。

insert(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。

搜索第一次走到 null 时，就是新关键字唯一合法的位置；在那里创建叶结点后把新子树根向上返回。

比较只递归进入一个孩子；重复关键字不改变结构，因此搜索路径之外的子树完全无需触碰。

递归返回时逐层 refresh 并返回当前根，使所有祖先的规模/高度与插入后的结构重新一致。

二叉搜索树删除：三种情况

三种情况： 叶结点直接删除；只有一个非空子树时由该子树接替；有两个非空子树时，用左子树最大值或右子树最小值替代，再递归删除替代结点。

删除代码

static <Key extends Comparable<? super Key>> Node<Key> remove(Node<Key> root, Key key) {
  if (root == null) {
    return null;
  }
  int comparison = key.compareTo(root.key);
  if (comparison < 0) {
    root.left = remove(root.left, key);
  } else if (comparison > 0) {
    root.right = remove(root.right, key);
  } else if (root.left != null && root.right != null) {
    Node<Key> successor = findMin(root.right);
    root.key = successor.key;
    root.right = remove(root.right, successor.key);
  } else {
    return root.left != null ? root.left : root.right;
  }
  refresh(root);
  return root;
}

remove(…) 从当前结构移除一个目标；操作结束时其余元素仍必须满足原来的表示不变量。

搜索路径若走到空子树，说明关键字不存在；返回 null 让父层保持原本的空链接，不制造额外结构变化。

目标较小或较大时只递归一侧；递归结果必须重新写回对应孩子，因为删除后那棵子树的入口可能已经换成别的结点。

命中两个孩子的结点时，用右子树最小关键字作为中序后继替代当前关键字，再删除后继原位置；若至多一个孩子，则直接让唯一孩子或 null 顶替当前结点。

结构删除完成后重新计算当前结点的缓存信息，并把“删除后的新子树根”返回给父层；这使二叉搜索树次序和规模/高度同时恢复一致。

顺序统计

带顺序统计的二叉搜索树

带顺序统计的二叉搜索树在每个结点增加 leftSize：

leftSize = |leftSubtree| + 1

用途：

查询第 \(k\) 小元素
查询某个关键字的排名
在有序集合中做顺序统计

第 k 小查询

static <Key extends Comparable<? super Key>> Node<Key> select(Node<Key> root, int zeroBasedRank) {
  if (root == null || zeroBasedRank < 0 || zeroBasedRank >= size(root)) {
    return null;
  }
  int leftSize = size(root.left);
  if (zeroBasedRank < leftSize) {
    return select(root.left, zeroBasedRank);
  }
  if (zeroBasedRank == leftSize) {
    return root;
  }
  return select(root.right, zeroBasedRank - leftSize - 1);
}

select(…) 利用子树规模直接跳过整棵子树，返回按中序排名为 k 的元素。

先排除空树和越界排名；随后 leftSize 直接告诉我们当前根之前有多少个更小关键字，也就是当前根在这棵子树中的 0-based 排名。

目标排名小于 leftSize 时，答案一定在左子树，而且它在左子树中的排名不变，因此只需递归左侧。

排名等于 leftSize 就命中当前根；更大时进入右子树，并扣掉已经跳过的“整个左子树 + 当前根”共 leftSize+1 个元素。

AVL 平衡树

二叉搜索树退化：插入顺序会决定树高

二叉搜索树插入本身没有任何“拉回平衡”的动作。若按递增顺序插入：

10, 20, 30, 40, 50, 60

每个新关键字都只能继续落到最右边。下面逐步看这棵完全合法的二叉搜索树怎样被插入顺序拉成一条链：

二叉搜索树退化意味着什么

二叉搜索树的查找、插入、删除本质上都是沿一条根到结点的路径工作，所以复杂度应写成 \(O(h)\)，不是天然的 \(O(\log n)\)。

树形较好时：\(h=O(\log n)\)；
递增 / 递减插入形成链时：\(h=n-1\)；
因此三种基本操作最坏都会变成 \(O(n)\)。

有序性还不够，我们还需要控制高度。

我们希望新的搜索树满足什么

理想的改进应该同时保住三件事：

仍然是二叉搜索树：中序遍历仍然递增，原来的查找规则不能失效；
局部修改：一次插入后不要重建整棵树，只修插入路径附近；
高度始终受控：不能允许某一侧长期比另一侧高很多。

AVL 的思路就是给二叉搜索树再加一个局部高度约束，并在约束被破坏时用旋转恢复它。

AVL 树定义：给二叉搜索树加一个局部约束

AVL 树首先仍然是一棵二叉搜索树；除此之外，对每一个结点都要求：

\[ |height(left)-height(right)|\le 1 \]

本课定义平衡因子为：

\[ bf(x)=height(right)-height(left) \]

因此合法值只有 \(-1,0,1\)。一旦某个结点变成 \(+2\) 或 \(-2\)，说明插入让这一局部子树失衡，必须修复。

注意：AVL 不是要求左右子树“完全一样高”，而是只允许高度差最多 1。

如何保持平衡

和二叉搜索树一样，先按关键字大小找到空位置并插入
插入的叶子结点会让祖先结点的高度发生变化
沿原搜索路径向上更新高度和平衡因子，直到第一个 \(|bf|=2\) 的祖先
根据“新结点落在这个失衡点的哪一侧”决定旋转方式

AVL 插入与旋转

四种失衡

旋转的本质是在保持中序顺序不变的前提下改变局部高度。

右单旋代码：逐行对应指针变化

static <Key extends Comparable<? super Key>> Node<Key> rotateWithLeftChild(Node<Key> oldRoot) {
  Node<Key> newRoot = Objects.requireNonNull(oldRoot.left, "left child");
  oldRoot.left = newRoot.right;
  newRoot.right = oldRoot;
  refresh(oldRoot);
  refresh(newRoot);
  return newRoot;
}

rotateWithLeftChild(…) 用一次右旋修复左左型失衡，同时重新计算受影响结点的高度。

LL 失衡时原左孩子将成为新的局部根；它原来的右子树位于两个关键字之间，是旋转时必须保留的“中间子树”。

先把中间子树接到 oldRoot.left，再让 oldRoot 成为 newRoot.right；中序关键字顺序完全不变，只改变局部高度。

结构变化后必须自下而上刷新：先更新已经下沉的 oldRoot，再更新新根；返回 newRoot 让父层接回旋转后的子树入口。

双旋为什么需要两步

LR / RL 的新结点落在“内侧”。例如 LR：失衡点 k3 的左边过高，但真正变高的是 k3.left 的右子树。如果直接右旋 k3，折线仍没有被正确展开。

因此先把内侧折线拉直，再做普通单旋：

对 k3.left 做一次左旋，把中间结点提上来；
局部形态变成 LL；
再对 k3 做右旋。

双旋代码：两次单旋

private static <Key extends Comparable<? super Key>> Node<Key> rotateWithRightChild(
    Node<Key> oldRoot) {
  Node<Key> newRoot = Objects.requireNonNull(oldRoot.right, "right child");
  oldRoot.right = newRoot.left;
  newRoot.left = oldRoot;
  refresh(oldRoot);
  refresh(newRoot);
  return newRoot;
}

static <Key extends Comparable<? super Key>> Node<Key> doubleWithLeftChild(Node<Key> root) {
  root.left = rotateWithRightChild(root.left);
  return rotateWithLeftChild(root);
}

左旋辅助函数是右旋的镜像：保留两个关键字之间的中间子树、改变局部根，并自下而上刷新缓存；整个过程中二叉搜索树的中序次序不变。

doubleWithLeftChild(…) 用左旋再右旋修复左右型失衡，使中间关键字成为新的局部根。

LR 失衡不能一次右旋解决：先左旋 root.left 把“内侧折线”变成 LL，再右旋原根。两个单旋组合后同时恢复局部高度和平衡。

AVL 高度界

设 \(N_h\) 是高度为 \(h\) 的 AVL 树最少结点数。

最坏形态的一侧高度为 \(h-1\)，另一侧高度为 \(h-2\)：

\[ N_h=N_{h-1}+N_{h-2}+1 \]

这与 Fibonacci 数同阶，因此：

\[ h=O(\log n) \]

AVL 的查找、插入、删除最坏都是 \(O(\log n)\)。

多路搜索

多路搜索树

\(m\) 路搜索树的每个内部结点最多有 \(m\) 个孩子，最多有 \(m-1\) 个关键字。

若某结点有关键字：

\[ k_1<k_2<\cdots<k_p \]

则孩子区间为：

\(C_0\)：小于 \(k_1\)
\(C_i\)：大于 \(k_i\) 且小于 \(k_{i+1}\)
\(C_p\)：大于 \(k_p\)

m 路搜索树示意

结点内用顺序或二分查找定位区间

B 树

为什么需要 B 树

二叉搜索树每个结点只有一个关键字、两个孩子。即使保持平衡，数据规模很大时仍需要经过较多层；如果结点存放在磁盘页（page）中，下降一层通常就意味着一次新的磁盘页访问。

B 树把多个有序关键字放进同一个磁盘页。一个结点可以把值域一次分成多个区间，因此扇出（fanout）远大于 2；在相同数据规模下，树通常更矮，查找需要访问的磁盘页也更少。

一棵 B 树长什么样

一个内部结点中有 k 个有序关键字，就把值域切成 k+1 段，因此必须有 k+1 个孩子指针。B 树的关键字本身可以对应记录，所以查找可能在内部结点直接命中。

B 树的定义

每个结点可能存储三种信息：关键字、关键字对应的数据指针、子结点指针
参数 t：中间结点只能有 \([t, 2t]\) 个子结点（至少有 t-1 个关键字，最多有 2t-1 个关键字）
根结点上界也是 2t-1 个关键字，但是没有下界
叶子结点不存子结点指针，可以多存一些关键字
整棵树中，所有叶子结点保持在同一深度（插入和删除过程自动保证）

本节示例取 t=2，所以非根结点允许 1..3 个关键字

B 树代码：整体定义

private static <Key extends Comparable<? super Key>, Value> int lowerBoundEntries(
    List<Entry<Key, Value>> entries, Key key) {
  int left = 0;
  int right = entries.size();
  while (left < right) {
    int middle = left + (right - left) / 2;
    if (entries.get(middle).key().compareTo(key) < 0) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }
  return left;
}

BTree(int maxKeys) {
  if (maxKeys < 3) {
    throw new IllegalArgumentException("maxKeys must be at least 3");
  }
  this.maxKeys = maxKeys;
}

Value search(Key key) {
  Objects.requireNonNull(key, "key");
  BNode<Key, Value> node = root;
  while (true) {
    int index = lowerBoundEntries(node.entries, key);
    if (index < node.entries.size() && node.entries.get(index).key().compareTo(key) == 0) {
      return node.entries.get(index).value();
    }
    if (node.isLeaf()) {
      return null;
    }
    node = node.children.get(index);
  }
}

磁盘页内关键字已排序；lowerBoundEntries 找到第一个不小于目标的位置，同时确定可能命中的记录与下一层孩子区间。

BTree(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。

maxKeys 只决定磁盘页何时溢出并分裂；它不改变关键字有序以及内部结点的区间划分规则。

search(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。

每个磁盘页先在页内定位：命中即返回，叶结点未命中即失败，内部结点只沿一个孩子下降；输入/输出次数主要由树高决定。

B 树查找

每到一个结点，先在结点内比较：若关键字命中当前记录，查找结束；否则根据关键字落在哪个区间，只沿一个孩子指针继续下降。

因此查找的两个层次是：结点内定位区间，然后树上下降一层。

B 树插入

下面固定 t=2，插入 63。待插入的结点如果超过 3 个关键字，就需要分裂。

分裂总是从叶子结点开始，并可能逐层向上传导。

B 树分裂代码：只在溢出后执行

private Split<Key, Value> splitNode(BNode<Key, Value> node) {
  int middle = node.entries.size() / 2;
  Entry<Key, Value> promoted = node.entries.get(middle);
  BNode<Key, Value> right = new BNode<>();

  right.entries.addAll(node.entries.subList(middle + 1, node.entries.size()));
  node.entries.subList(middle, node.entries.size()).clear();
  if (!node.isLeaf()) {
    right.children.addAll(node.children.subList(middle + 1, node.children.size()));
    node.children.subList(middle + 1, node.children.size()).clear();
  }
  return new Split<>(promoted, right);
}

splitNode(…) 把溢出的 B 树结点分成两个合法结点，并把中间关键字提升给父结点。

溢出后选中间记录作为向父层提升的分隔项，并建立新的右结点；这个中间记录将不再留在左右两个孩子中。

右半记录移到新结点，中间记录从孩子中移走并提升到父结点；这就是 B 树分裂中的上移。

内部结点分裂时还要在同一边界切开孩子指针；返回 promoted + right 供父层接入。

B 树插入核心：从叶结点开始，分裂向上传导

private Split<Key, Value> insertRec(BNode<Key, Value> node, Key key, Value value) {
  int index = lowerBoundEntries(node.entries, key);
  if (index < node.entries.size() && node.entries.get(index).key().compareTo(key) == 0) {
    node.entries.set(index, new Entry<>(key, value));
    return null;
  }

  if (node.isLeaf()) {
    node.entries.add(index, new Entry<>(key, value));
  } else {
    Split<Key, Value> childSplit = insertRec(node.children.get(index), key, value);
    if (childSplit != null) {
      node.entries.add(index, childSplit.promoted());
      node.children.add(index + 1, childSplit.right());
    }
  }
  return node.entries.size() > maxKeys ? splitNode(node) : null;
}

insertRec(…) 递归下降到目标子树，并把下层分裂产生的提升键逐层向上传播。

先在当前磁盘页内定位关键字；已有关键字只更新值，不改变关键字数量，因此不会产生分裂。新关键字才继续寻找真正的插入位置。

叶结点是真实新增记录的地方；若当前结点不是叶结点，就只沿下界对应的一个孩子递归下降。

孩子分裂后父磁盘页接入提升键与右孩子；只有父磁盘页也溢出才继续分裂，因此分裂逐层向上传播。

B 树插入入口与页内二分

void insert(Key key, Value value) {
  Objects.requireNonNull(key, "key");
  Objects.requireNonNull(value, "value");
  Split<Key, Value> split = insertRec(root, key, value);
  if (split != null) {
    BNode<Key, Value> oldRoot = root;
    BNode<Key, Value> newRoot = new BNode<>();
    newRoot.entries.add(split.promoted());
    newRoot.children.add(oldRoot);
    newRoot.children.add(split.right());
    root = newRoot;
  }
}

insert(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。

顶层入口把真正的插入和普通磁盘页分裂全部交给递归过程；返回 null 表示旧根仍能容纳结果，树高不变。

只有根分裂时没有父磁盘页接住提升键；此时新建根指向旧根与右孩子，树高才增加 1。

B 树删除

删除仍取 t=2，所以非根结点删除后至少要保留 t-1=1 个关键字。先删除；如果删除让结点低于容量下界，就通过借位（borrow）或合并（merge）修复。

兄弟结点还有多余关键字：借位。兄弟结点的边界记录上移到父结点，同时父结点的分隔记录下移到容量不足的结点；
兄弟结点也在下界：合并。父结点的分隔记录下移，与两个相邻孩子合成一个结点；父结点因此少一个关键字和一个孩子指针；
父结点若因此也少于 t-1 个关键字：同样的容量不足继续向上传导；
如果传播到根，并且根最后没有关键字，只剩一个孩子：这个孩子接替根，树高减 1。

B 树删除

插入只能发生在叶子结点，然后把分裂结果向上传导。

删除可以发生在任意位置，需要借位和合并。

B+ 树

B+ 树：为范围查询和更高扇出而来

B 树的关键字记录本身可以带数据指针；这让内部磁盘页能直接命中记录，但也会占用原本可以放孩子指针的磁盘页空间。磁盘页大小固定时，内部磁盘页能容纳的孩子指针越少，扇出越小，树越高，查找需要访问的磁盘页也可能更多。

另一个问题是范围查询：B 树查到起点后，不能简单沿叶层顺序扫描；后续关键字可能分布在内部记录与不同子树中，范围查询往往需要继续做树遍历或反复定位。

B+ 树的定义

非叶结点以“下界关键字 + 孩子指针”一一成对保存导航信息，不存储真实数据记录；非根内部磁盘页有 t..2t 对，本节 t=2 即 2..4 对
真实的“关键字 + 数据指针”只保存在叶结点；非根叶结点有 t-1..2t-1 个数据项，本节即 1..3 个
所有叶结点保持在同一深度，并通过 next 串成有序链

B+ 树代码：整体定义

private static <Key extends Comparable<? super Key>> int lowerBoundKeys(
    List<Key> keys, Key key) {
  int left = 0;
  int right = keys.size();
  while (left < right) {
    int middle = left + (right - left) / 2;
    if (keys.get(middle).compareTo(key) < 0) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }
  return left;
}

private static <Key extends Comparable<? super Key>> int childIndex(
    List<Key> lowerBounds, Key key) {
  int left = 0;
  int right = lowerBounds.size();
  while (left < right) {
    int middle = left + (right - left) / 2;
    if (lowerBounds.get(middle).compareTo(key) <= 0) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }
  return Math.max(0, left - 1);
}

private BPlusNode<Key, Value> findLeaf(Key key) {
  BPlusNode<Key, Value> node = root;
  while (!node.leaf) {
    node = node.children.get(childIndex(node.keys, key));
  }
  return node;
}

BPlusTree(int maxEntries) {
  if (maxEntries < 3) {
    throw new IllegalArgumentException("maxEntries must be at least 3");
  }
  this.maxEntries = maxEntries;
}

Value search(Key key) {
  Objects.requireNonNull(key, "key");
  BPlusNode<Key, Value> leaf = findLeaf(key);
  int index = lowerBoundKeys(leaf.keys, key);
  if (index < leaf.keys.size() && leaf.keys.get(index).compareTo(key) == 0) {
    return leaf.values.get(index);
  }
  return null;
}

lowerBoundKeys 在叶页找到第一个不小于目标的位置；同一个位置既用于判断精确命中，也用于确定新关键字的插入点。

内部关键字表示孩子的下界；childIndex 寻找最后一个不大于目标的下界，因此只需下降到一个候选孩子。

findLeaf(…) 按分隔键选择孩子，直到到达实际保存数据项的叶结点。

findLeaf 只沿内部索引下降；真实记录不会在途中返回，直到叶结点才结束导航。

BPlusTree(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。

maxEntries 只控制磁盘页何时溢出并分裂；它不改变“内部结点只导航、叶结点才存真实关键字和值”的分工。

search(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。

单点查询下降到叶结点后做下界精确匹配；真实值只在叶结点中读取。

B+ 树查找

B 树的范围查询

B 树的真实“关键字 + 数据地址”记录既可能在叶结点，也可能在内部磁盘页。查询同一个区间 [22,57] 时，找到左端点附近后仍要按关键字顺序继续遍历，并在访问完一个孩子后回溯到父结点，因为父结点自己也可能包含范围内的记录。

B+ 树的范围查询

查询区间 [22,57]：先分别定位左右端点所在的叶结点。之后不需要再回到内部树结构，只要从左端点所在叶结点开始，沿 next 从左到右扫描，直到超过右端点。

B+ 树插入：叶结点分裂采用复制上移

插入 53。

注意：分裂还必须修复叶结点之间的 next 链。

B+ 树分裂代码

private Split<Key, Value> splitLeaf(BPlusNode<Key, Value> leaf) {
  int middle = (leaf.keys.size() + 1) / 2;
  BPlusNode<Key, Value> right = new BPlusNode<>(true);
  right.keys.addAll(leaf.keys.subList(middle, leaf.keys.size()));
  right.values.addAll(leaf.values.subList(middle, leaf.values.size()));
  leaf.keys.subList(middle, leaf.keys.size()).clear();
  leaf.values.subList(middle, leaf.values.size()).clear();
  right.next = leaf.next;
  leaf.next = right;
  return new Split<>(right.keys.get(0), right);
}

splitLeaf(…) 把溢出的 B+ 树叶结点分裂，同时维护叶层顺序链和父结点分隔键。

叶结点溢出后按中间位置建立新的右叶；关键字和值必须成对移动，因为真实记录只存在于叶层。

后半关键字和值移到右叶；右叶最小关键字仍保留在叶结点中，父层拿到的只是它的副本，这就是复制上移。

分裂还必须把新右叶插进原有 next 链：先继承原后继，再让左叶指向新右叶；返回的下界与右页供父层新增导航对。

B+ 树插入核心代码

private static <Key extends Comparable<? super Key>, Value> Key minKey(
    BPlusNode<Key, Value> node) {
  while (!node.leaf) {
    node = node.children.get(0);
  }
  if (node.keys.isEmpty()) {
    throw new IllegalStateException("non-root subtree must not be empty");
  }
  return node.keys.get(0);
}

private Split<Key, Value> splitInternal(BPlusNode<Key, Value> node) {
  int middle = node.children.size() / 2;
  BPlusNode<Key, Value> right = new BPlusNode<>(false);
  right.keys.addAll(node.keys.subList(middle, node.keys.size()));
  right.children.addAll(node.children.subList(middle, node.children.size()));
  node.keys.subList(middle, node.keys.size()).clear();
  node.children.subList(middle, node.children.size()).clear();
  return new Split<>(right.keys.get(0), right);
}

private Split<Key, Value> insertRec(BPlusNode<Key, Value> node, Key key, Value value) {
  if (node.leaf) {
    int index = lowerBoundKeys(node.keys, key);
    if (index < node.keys.size() && node.keys.get(index).compareTo(key) == 0) {
      node.values.set(index, value);
      return null;
    }
    node.keys.add(index, key);
    node.values.add(index, value);
    return node.keys.size() > maxEntries ? splitLeaf(node) : null;
  }

  int childIndex = childIndex(node.keys, key);
  Split<Key, Value> childSplit = insertRec(node.children.get(childIndex), key, value);
  node.keys.set(childIndex, minKey(node.children.get(childIndex)));
  if (childSplit != null) {
    node.keys.add(childIndex + 1, childSplit.lowerBound());
    node.children.add(childIndex + 1, childSplit.right());
  }
  return node.children.size() > maxEntries ? splitInternal(node) : null;
}

minKey 沿最左孩子走到叶结点，得到子树下界；内部磁盘页据此刷新对应孩子的导航关键字。

splitInternal(…) 分裂溢出的内部结点并向上传递分隔键，使每层继续满足阶数约束。

内部结点分裂必须成对切分“下界 + 孩子”；父层用新右页的最小关键字与右页新增一对导航信息。

insertRec(…) 递归下降到目标子树，并把下层分裂产生的提升键逐层向上传播。

只有叶结点分支才真正新增或更新记录：已有关键字只改值，新关键字才插入；只有叶结点超容量时才执行复制上移分裂。

内部结点分支只递归一个孩子；返回后仍要刷新它的下界，因为插入可能改变该子树的最小关键字。

孩子分裂时插入新的“下界 + 右孩子”；只有当前磁盘页也溢出，分裂才继续向上传播。

B+ 树插入入口与页内二分

void insert(Key key, Value value) {
  Objects.requireNonNull(key, "key");
  Objects.requireNonNull(value, "value");
  Split<Key, Value> split = insertRec(root, key, value);
  if (split != null) {
    BPlusNode<Key, Value> oldRoot = root;
    BPlusNode<Key, Value> newRoot = new BPlusNode<>(false);
    newRoot.keys.add(minKey(oldRoot));
    newRoot.children.add(oldRoot);
    newRoot.keys.add(split.lowerBound());
    newRoot.children.add(split.right());
    root = newRoot;
  }
}

insert(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。

顶层把普通插入和所有非根分裂交给递归过程；若没有分裂传播到根，树高和根入口都保持不变。

根分裂时新建内部根结点；旧根的最小关键字与新右结点的下界分别导航两个孩子。

B+ 树删除

真实记录只在叶结点中删除。删除后回溯更新各子树下界。若发生下溢，考虑借位或合并，并保持叶结点的 next 链连续。

B 树与 B+ 树对照

高扇出直觉：为什么树可以很矮

真实数据库索引页往往可以容纳大量“下界关键字 + 孩子指针”导航对；扇出越大，同样数据量所需的高度越低。

图中的省略号表示大量未画出的兄弟磁盘页和叶磁盘页。由于内部磁盘页不存真实记录，B+ 树通常能获得更高扇出；在相同磁盘页大小和数据规模下，这往往意味着更低的树高与更少的根到叶磁盘页输入/输出。

为什么数据库常用 B+ 树

数据库索引既关心单点查询，也关心范围扫描和磁盘页输入/输出。
B+ 树的内部磁盘页不携带记录数据，同样大小的页通常可以放更多“下界关键字 + 孩子指针”导航对，扇出更高
叶层链表让范围查询定位起点后可以连续顺序扫描

本章小结

二叉搜索树把左小右大的全局有序性作为不变量，查找、插入、删除都沿搜索路径修改局部结构。
二叉搜索树的查找成本由树高决定；极端插入顺序会把树退化为线性链。
带顺序统计的二叉搜索树在结点中维护 leftSize，把“第 \(k\) 小”查询转化为沿路径比较左子树规模。
AVL 树用平衡因子限制局部高度差，通过单旋和双旋恢复平衡，并保持对数高度界。
多路搜索树用多个关键字把子树划分成多个区间，核心收益来自更大的扇出。
B 树的阶、结点容量和叶层一致性共同保证磁盘页访问路径足够短。
B 树可在内部结点保存真实记录；B+ 树的内部磁盘页只存索引副本、叶磁盘页存数据并串联，因此更适合范围查询。

下载本章完整 Gradle 工程

本章习题

习题 1：插入二叉搜索树：把序列 \(3,1,4,6,9,2,5,7\) 依次插入一棵空二叉搜索树，画出最终搜索树。
习题 2：检测二叉搜索树：给定一棵二叉树，设计方法判断它是否满足二叉搜索树的全局有序性质，并说明为什么只比较父子结点不够。
习题 3：路径三集合判断：在有序集 \(S\) 的二叉搜索树中，沿一条根到叶路径把结点分成路径左侧、路径上、路径右侧三组。判断三组元素是否一定具有全局大小顺序，并说明理由。
习题 4：AVL 最少结点数：设 \(N_h\) 为高度 \(h\) 的 AVL 树的最少结点数。建立递推关系，并据此说明 AVL 树高度与结点数 \(n\) 的关系。
习题 5：B 树与 B+ 树：内部结点只存索引、所有数据都在叶子、叶子按关键字链接，这是什么树？

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦

第 4.1 章 树索引

引入

索引树需要特殊设计

学习目标

本章路线图

二叉搜索树

二叉搜索树定义

二叉搜索树示例

查找操作

二叉搜索树：查找代码与复杂度

findMin 与 findMax

findMin / findMax 代码

二叉搜索树插入

二叉搜索树插入代码

二叉搜索树删除：三种情况

删除代码

顺序统计

带顺序统计的二叉搜索树

第 k 小查询

AVL 平衡树

二叉搜索树退化：插入顺序会决定树高

二叉搜索树退化意味着什么

我们希望新的搜索树满足什么

AVL 树定义：给二叉搜索树加一个局部约束

如何保持平衡

AVL 插入与旋转

四种失衡

右单旋代码：逐行对应指针变化

双旋为什么需要两步

双旋代码：两次单旋

AVL 高度界

多路搜索

多路搜索树

m 路搜索树示意

B 树

为什么需要 B 树

一棵 B 树长什么样

B 树的定义

B 树代码：整体定义

B 树查找

B 树插入

B 树分裂代码：只在溢出后执行

B 树插入核心：从叶结点开始，分裂向上传导

B 树插入入口与页内二分

B 树删除

B 树删除

B+ 树

B+ 树：为范围查询和更高扇出而来

B+ 树的定义

B+ 树代码：整体定义

B+ 树查找

B 树的范围查询

B+ 树的范围查询

B+ 树插入：叶结点分裂采用复制上移

B+ 树分裂代码

B+ 树插入核心代码

B+ 树插入入口与页内二分

B+ 树删除

B 树与 B+ 树对照

高扇出直觉：为什么树可以很矮

为什么数据库常用 B+ 树

本章小结

本章习题

致谢

第 4.1 章树索引

`findMin` 与 `findMax`

`findMin` / `findMax` 代码