B+ 树是自平衡树的高级形式，其中所有值都存在于叶级中。
在学习 B+ 树之前要理解的一个重要概念是多级索引。在多级索引中，索引的索引创建如下图所示。它使访问数据更容易、更快捷。
B+树的特点
- 所有叶子都处于同一水平。
- 根节点至少有两个孩子。
- 除root外的每个节点最多可以有m孩子们，至少m/2孩子们。
- 每个节点最多可以包含m- 1键和至少[m/2⌉ - 1键。
B树和B+树的比较
B树
B+tree
数据指针仅出现在 B+ 树的叶节点上，而数据指针出现在 B 树的内部、叶或根节点中。
叶子在 B-tree 上不相互连接，而在 B+ 树上是相互连接的。
B+树上的操作比B树上的要快。
在 B+ 树上搜索
按照以下步骤在 B+ 顺序树中搜索数据米. 让要搜索的数据为ķ.
- 从根节点开始。将 k 与根节点的键进行比较[k1, k2, k3,......km- 1].
- 如果k < k1，到根节点的左孩子。
- 否则，如果k == k1， 比较ķ2.如果k < k2, k 介于ķ1和ķ2.所以，在左孩子中搜索ķ2.
- 如果k > k2， 去做k3, k4,...km-1如第 2 步和第 3 步。
- 重复上述步骤，直到到达叶节点。
- 如果叶节点中存在k，则返回true，否则返回false。
在 B+ 树上搜索示例
在下面的 B+ 树上搜索k = 45
- 将 k 与根节点进行比较。
- 由于 k > 25，去右节点查找。
- 将 k 与 35 进行比较。由于 k > 30，因此将 k 与 45 进行比较
- 由于 k ≥ 45，所以去右孩子。
- k 被发现。
B+ 树上的插入节点
将元素插入B+树有以下3个步骤
- 搜索适当的叶子节点
- 插入元素
- 平衡/拆分树
插入操作
在将元素插入 B+ 树之前，必须牢记这些属性。
- 根节点至少有两个孩子。
- 除root外的每个节点最多可以有m个子节点，至少m/2个子节点。
- 每个节点最多可以包含m- 1个 键和至少⌈m/2⌉ - 1键。
案例一
- 如果叶子未满，则按递增顺序将元素插入叶子节点。
案例二
- 如果叶子已满，则将密钥按升序插入叶子节点，并按以下方式平衡树。
- 打破节点m/2th位置。
- 添加m/2th也是父节点的键。
- 如果父节点已满，请执行步骤 2 至 3。
插入示例
让我们通过下面的插图来理解插入操作。
要插入的元素是 5,15,25,35,45。
- 插入5
- 插入15
- 插入25
- 插入35
- 插入45
从 B+ 树中删除元素
删除操作
在执行以下步骤之前，必须了解有关度为m的 B+ 树的这些属性。
- 一个节点最多可以有 m 个子节点。
- 一个节点最多可以包含多个m - 1键。
- 一个节点应该有最少的⌈m/2⌉孩子。
- 一个节点（除了根节点）应该包含最少的⌈m/2⌉ - 1键。
在删除键时，我们还必须注意内部节点（即索引）中存在的键，因为这些值在 B+ 树中是冗余的。搜索要删除的密钥，然后按照以下步骤操作。
案例一
要删除的键仅存在于叶节点而不存在于索引（或内部节点）中。它有两种情况：
- 节点中的键数量超过了最小数量。只需删除元素。 从 B-tree 中删除 40
- 节点中有确切的最小键数。删除密钥并从直接兄弟那里借用密钥。将兄弟节点的中间键添加到父节点。从 B-tree 中删除 5
案例二
要删除的密钥也存在于内部节点中。然后我们也必须从内部节点中删除它们。这种情况有以下几种情况。
- 如果节点中的键数超过最小数量，只需从叶节点中删除该键，并从内部节点中删除该键。用中序后继填充内部节点中的空白区域。从 B-tree 中删除 45
- 如果节点中有确切的最小键数，则删除该键并从其直接兄弟（通过父级）借用一个键。用借来的键填充索引（内部节点）中创建的空白空间。
- 这种情况与情况 (1) 类似，但此处在直接父节点上方生成空白空间。
删除键后，将空白空间与其兄弟合并。
用中序后继填充祖父节点中的空白空间。从 B-tree 中删除 25
案例三
在这种情况下，树的高度会缩小。这有点复杂。从下面的树中删除 55 会导致这种情况。在下面的插图中可以理解。从 B-tree 中删除 55
参考文章
