共计 1764 个字符，预计需要花费 5 分钟才能阅读完成。
文章首发于「陈树义」公众号及集体博客 shuyi.tech
均衡二叉树的查找效率是十分高的，并能够通过升高树的深度来进步查找的效率。然而当数据量十分大，树的存储的元素数量是无限的，这样会导致二叉查找树结构因为树的深度过大而造成磁盘 I/O 读写过于频繁，进而导致查问效率低下。
而 B 树的呈现是为了解决这个问题，其能够一次性读入许多数据。一个节点不再只是存储一个数值，而是存储一个分片的数据。这样就能够防止频繁去读取磁盘数据，造成频繁的 IO 拜访，造成查找速度瓶颈。
B 树
B-Tree 其实就是 B 树，很多人都会说成 B 减树，其实是错的，要留神。
B 树不要和二叉树混同，B 树不是二叉树，而是一种自均衡树数据结构。 它保护有序数据并容许以对数工夫进行搜寻，程序拜访，插入和删除。B 树是二叉搜寻树的一般化，因为 B 树的节点能够有两个以上的子节点。
与其余自均衡二进制搜寻树不同，B 树非常适合读取和写入绝对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统，例如 mysql 的 InnoDB 引擎应用的数据结构就是 B 树的变形 B+ 树。
B 树是一种均衡的多分树，通常咱们说 m 阶的 B 树，它必须满足如下条件：
- 每个节点最多只有 m 个子节点。
- 每个非叶子节点（除了根）具备至多 ⌈m/2⌉ 子节点。
- 如果根不是叶节点，则根至多有两个子节点。
- 具备 k 个子节点的非叶节点蕴含 k -1 个键。
- 所有叶子都呈现在同一程度，没有任何信息（高度一致）。
B 树的阶，指的是 B 树中节点的子节点数目的最大值。例如在上图的书中，「13,16,19」领有的子节点数目最多，一共有四个子节点（灰色节点）。所以该 B 树的阶为 4，该树称为 4 阶 B 树。在理论利用中，B 树利用于 MongoDb 的索引。
B+ 树
B+ 树是应文件系统所需而产生的 B 树的变形树。B+ 树的特色：
- 有 m 个子树的两头节点蕴含有 m 个元素（B 树中是 k-1 个元素），每个元素不保留数据，只用来索引。
- 所有的叶子结点中蕴含了全副关键字的信息，及指向含有这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大的程序链接。而 B 树的叶子节点并没有包含全副须要查找的信息。
- 所有的非终端结点能够看成是索引局部，结点中仅含有其子树根结点中最大（或最小）关键字。而 B 树的非终节点也蕴含须要查找的无效信息。例如下图中的根节点 8 是左子树中最大的元素，15 是右子树中最大的元素。
与 B 树相比，B+ 树有着如下的益处：
- B+ 树的磁盘读写代价更低
B+ 树的外部结点并没有指向关键字具体信息的指针，所以其外部结点绝对 B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多，所以一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了，查找速度就更快了。
- B+ 树查问效率更加稳固
因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以 B+ 树中任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。而对于 B 树来说，因为其每个节点都存具体的数据，因而其查问速度可能更快，然而却并不稳固。
- B+ 树便于范畴查问（最重要的起因，范畴查找是数据库的常态）
B 树在进步了 IO 性能的同时，并没有解决元素遍历效率低下的问题。为了解决这个问题，B+ 树利用而生。B+ 树只须要去遍历叶子节点就能够实现整棵树的遍历。在数据库中基于范畴的查问是十分频繁的，因而 MySQL 的 Innodb 引擎就应用了 B+ 树作为其索引的数据结构。
总结
B 树是为了解决大数据量的查找问题而诞生的，其实二叉搜寻树的一般化。通过每个节点存储更多的数据，使得 B 树比起二叉搜寻树更加扁平化，从而缩小 IO 读取频次，进步搜寻速度。
B+ 树比起 B 树，最大的差别是非叶子节点不再存储具体数据，以及叶子节点是链表构造。非叶子节点不再存储具体数据，这使得 B+ 树更加扁平化，查找效率更高。叶子节点是链表构造，这使得 B+ 树更适宜用在范畴查找的场景中。
学到这里，咱们的树结构小道基本上学完了，来整体复习一下吧。
参考资料
- B 树_百度百科
- B + 树_百度百科
- 对于 B /B+ 树的比照。
- B 树、B + 树详解 – Assassin の – 博客园
- 漫画 B 树 B – 树_sinat_36118365 的博客 – CSDN 博客
- 漫画：什么是 B + 树？– 知乎
- 【原创】MySQL (Innodb) 索引的原理 – 孤单烟 – 博客园
