跳转至

B+ 树

B+ 树是 B 树的变形树，更适合与文件索引系统

1 B+ 树使用场景

B+ 树通常用于 数据库 和操作系统的 文件系统 中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和 BFS 等文件系统都在使用 B+ 树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

2 B+ 的特性

  1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；（叶节点使用指针连接成链表，范围查询更加高效。）
  2. 不可能在非叶子结点命中；
  3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
  4. 更适合文件索引系统；
  5. 通常在 B+ 树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

3 B+ 树优缺点

优点： 1. 树的高度小

4 B+ 树和 B 树的优缺点比较

B+ 树和 B 树都是一种多路搜索树，可以用来实现关系数据库中的索引。B+ 树叶子节点构成链表，更利用 范围查找和排序。而 B 树进行范围查找和排序则要对树进行递归遍历。 B 树与 B+ 树比较：  1. B+ 树层级更少，查找更快。 2. B+ 树查询速度稳定：由于 B+ 树所有数据都存储在叶子节点，所以查询任意数据的次数都是树的高度 h。 3. B+ 树有利于范围查找。 4. B+ 树全节点遍历更快：所有叶子节点构成链表，全节点扫描，只需遍历这个链表即可。 5. B 树优点：如果在 B 树中查找的数据离根节点近，由于 B 树节点中保存有数据，那么这时查询速度比 B+ 树快。

4.1 B 树优点

B 树适合用于存储大量数据的场合，其优点包括： - 每个节点可以存储更多的键值对，减少了内存访问次数，提高了性能； - 叶子节点之间没有指针，只有顺序访问指针，可以提高顺序读取的性能； - 插入和删除操作相对简单，只需要从叶子节点开始，不需要移动整个节点中的元素； - 相对于平衡二叉树而言，B 树的高度更低，因此查找速度更快。

4.2 B+ 树优点

B+ 树在 B 树的基础上进行了改进，其优点包括： - 内部节点只存储键，不存储数据，降低了内部节点的大小，使得一次读取更多的键，从而提高了性能； - 所有数据都存储在叶子节点上，叶子节点之间通过链表相连，便于范围查询； - 叶子节点之间可以使用二分查找，提高范围查询的效率； - 相对于 B 树而言，B+ 树的查询效率更稳定，更适合很大的数据集合。

4.3 B树和 B+ 树的不同点

B 树和 B+ 树的不同点主要在于内部节点的设计和数据的存储方式： - B 树的内部节点既存储键又存储数据，可以直接作为查询结果。而 B+ 树的内部节点只存储键，必须通过叶子节点才能获取数据。 - B 树每个节点同时存储键和数据，因此每个节点的大小相对较大。B+ 树的叶子节点存储所有的数据，而内部节点只存储键，因此每个节点的大小相对较小。

5 B+ 树定义

一棵 m 阶的 B+ 树和 m 阶的 B 树的差异在于： 1. 有 n 棵子树的结点中含有 n 个关键字；（B 树是含有 n-1 个关键字） 2. 所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接： 3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大或最小关键字。

3阶B+树

6 B+ 树的查找、插入和删除

B+数的查询、插入、删除，最终都要到叶子结点

在 B+ 树上进行随机查找、插入和删除的过程基本上与 B- 树类似。 1. 查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在 B+ 树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。B+ 树查找的分析类似于 B 树。B+ 树不仅能够有效地查找单个关键字，而且更适合查找某个范围内的所有关键字。例如，在 B+ 树上找出范围在 [a,b] 之间的所有关键字值。处理方法如下：通过一次查找找出关键字 a,不管它是否存在，都可以到达可能出现 a 的叶子结点，然后在叶子结点中查找关键字值等于 a 或大于的那些关键字，对于所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。如果在当前结点中没有发现大于 b 的关键字，就可以使用当前叶子结点的最后一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于 b 的关键字，才停止查找。 2. 插入：仅在叶子结点上进行插入，当结点中的关键字个数大于 m 时要分裂成两个结点，平分关键字，并且，它们的双亲结点中应同时包含这两个结点中的最大关键字。 3. 删除：B+ 树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于 [m/2] 时，其和兄弟结点的合并过程亦和 B 树类似。

7 mysql 中 B+ 树结构是怎么存储在磁盘上的

参考 为什么大家说 mysql 数据库单表最大两千万？依据是啥？ - Mysql 将数据储存在硬盘上，为了提高查询速度，比较好的做法是将索引数据和一部分热数据（经常访问的数据）放到内存中（Mysql 的 Buffer Poll）。 - 下图是 InnoDB 逻辑储存结构

8 B+ 树实现源码

参考 https://github.com/begeekmyfriend/bplustree