# B-Tree 简述

## 度的定义

B-Tree 预定义了一个「树的度（degree ）」的范围。当在节点中插入或删除数据时，「节点的度」就会变化，但仅限制在 B-Tree 预定义的范围之内变化。

为了维持预定义的「树的度」的范围，B-Tree 的内部节点可能被合并或分离。因为「节点的度」可以在一定范围内盖改变，所以 B-Tree 可以不像其它「自平衡搜索树」一样，需要经常重新平衡树的内部节点。不过 B-Tree 可能会浪费一些存储空间，因为它的内部节点可能是不满的。

B-Tree 「树的度」的上限和下限，对某一特定的实现来说通常是固定的。例如 2-3 B-Tree 的每一个内部节点的度仅可能只有 2 或 3 个子节点。

## 节点内部

每个 B-Tree 的内部节点可以包含多个 key，key 用作为分离内部节点的「子树」的分离值。例如，如果一个 B-Tree 的内部节点拥有 3 个子节点（即子树），那么它就有拥有 2 个 key ：a1 和 a2。左侧子树中的 key 小于 a1，中部子树中的 key 大于 a1 并小于 a2，右侧子树中的 key 大于 a2。

通常来说，key 的个数会介于 d \~ 2d 之间，d+1 是「树的度」。在实际应用中，key 往往占用了节点的大部分空间。系数 2 可以保证节点被正常分离或组合。当向一个拥有 2d 个 key 的内部节点添加一个 key 时，B-Tree 将会这 2d+1 个 key 分离成 2 节点，并且将处于中间位置的 key 移动至父节点中。至此，每个被分离的节点都拥有最小数量的 key。类似的，当向两个相邻且都拥有 d 个 key 的内部节点删除一个 key 时，B-Tree 则会组合这两个相邻的节点。删除一个 key 会导致内部节点仅有 d-1 个 key。组合两个相邻的节点时，会从其父节点中取出一个 key 与它们组成一个拥有 2d 个 key 的节点。

节点的「子树」个数会比节点的 key 个数多一个。在 2-3 B-Tree 中，内部节点将会存储 1 个或 2 个 key，同时会存储 2 个子树或 3 个子树。一棵 B-Tree 树的上限和下限，有时候会被参数化成 (d + 1) - (2d + 1) ，或者更简单地仅以 (2d + 1) 来描述。

## 维持平衡

B-Tree 通过要求所有的「叶子节点」都保持相同的深度，来维持树的平衡。「树的深度」会随着元素的添加而缓慢增加，然而 B-Tree 「树的深度」整体性的增加是不常见的，这会导致树中所有的「叶子节点」离「树根」更远了一个节点。

## 参考资料

* [B数 - 维基百科](https://zh.wikipedia.org/wiki/B%E6%A0%91)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gitbook.fantasticmao.cn/tech/shu-ju-ku/mysql/btree-jian-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.