B+树简介

为了实现动态多级索引， B-树 一般采用B+树。然而，用于索引的B-tree的缺点是，它将对应于特定键值的数据指针（指向包含键值的磁盘文件块的指针）与该键值一起存储在B-tree的节点中。这种技术大大减少了可以打包到B树节点中的条目数量，从而增加了B树中的级别数量，从而增加了记录的搜索时间。

B+树通过只在树的叶节点存储数据指针，消除了上述缺点。因此，B+树的叶节点结构与B-树的内部节点结构有很大不同。这里可以注意到，由于数据指针仅存在于叶节点处，因此叶节点必须存储所有键值及其到磁盘文件块的对应数据指针，以便访问它们。此外，叶节点被链接以提供对记录的有序访问。因此，叶节点构成第一级索引，内部节点构成多级索引的其他级别。叶节点的一些键值也出现在内部节点中，只是作为控制记录搜索的媒介。

从上面的讨论可以明显看出，与B-树不同，B+树有两个顺序，“a”和“B”，一个用于内部节点，另一个用于外部（或叶）节点。

“a”级B+树的内部节点结构如下：

1. 每个内部节点的形式如下：

   1. K _1. ，P _2. K _2. , ….., P _c-1 K _c-1 P _C > 其中c<=a，且每个 P _我 是树指针（即指向树的另一个节点） 而且，每个 K _我 这是一个关键值 （参考图1）。
2. 每个内部节点都有：K _1. 2. < …. < K _c-1
3. 对于P指向的子树中的每个搜索字段值“X” _我 ，以下条件成立： K _i-1 我 ，对于1 K _i-1 （参考图一）
4. 每个内部节点最多有“a”树指针。
5. 根节点至少有两个树指针，而其他内部节点至少各有一个ceil（a/2）树指针。
6. 如果任何内部节点都有“c”指针，c<=a，那么它就有“c–1”键值。

图一

“B”级B+树的叶节点结构如下：

1. 每个叶节点的形式如下： < 1. D _1. >， 2. D _2. >, ….., c-1 D _c-1 >，P _下一个 > 其中c<=b，且每个 D _我 是一个数据指针（即指向磁盘中键值为K的实际记录） _我 或包含该记录的磁盘文件块） 而且，每个 K _我 这是一个关键值 和 P _下一个 指向B+树中的下一个叶节点 （参考图二）。
2. 每个叶节点都有：K _1. 2. < …. < K _c-1 ，c<=b
3. 每个叶节点至少有ceil（b/2）值。
4. 所有叶节点都处于同一级别。

图二

使用P _下一个 指针它可以像链表一样遍历所有叶节点，从而实现对存储在磁盘中的记录的有序访问。

B+树图-

优势—— 与具有相同“l”级别的B树相比，具有“l”级别的B+树可以在其内部节点中存储更多条目。这突出了对任何给定密钥的搜索时间的显著改进。具有较低的水平和P的存在 _下一个 指针意味着B+树在从磁盘访问记录时非常快速高效。