共计 2531 个字符，预计需要花费 7 分钟才能阅读完成。
背景
首先，来谈谈 B 树。为什么要应用 B 树？咱们须要明确以下两个事实：
【事实 1】
不同容量的存储器，访问速度差别迥异。以磁盘和内存为例，拜访磁盘的工夫大略是 ms 级的，拜访内存的工夫大略是 ns 级的。有个形象的比喻，若一次内存拜访须要 1 秒，则一次外存拜访须要 1 天。所以，当初的存储系统，都是分级组织的。
最罕用的数据尽可能放在更高层、更小的存储器中，只有在以后层找不到，才向更低层、更大的存储器中寻找。这也就解释了，当解决大规模数据的时候（指无奈将数据一次性存入内存），算法的理论运行工夫，往往取决于数据在不同存储级别之间的 IO 次数。因而，要想晋升速度，关键在于缩小 IO。
【事实 2】
磁盘读取数据是以数据块(block)（或者：页，page）为根本单位的，位于同一数据块中的所有数据都能被一次性全副读取进去。
换句话说，从磁盘中读 1B，与读 1KB 简直一样快！因而，想要晋升速度，应该利用外存批量拜访的特点，在一些文章中，也称其为磁盘预读。零碎之所以这么设计，是基于一个驰名的局部性原理：
当一个数据被用到时，其左近的数据也通常会马上被应用，程序运行期间所须要的数据通常比拟集中
B 树
假如有 10 亿条记录（100010001000），如果应用均衡二叉搜寻树（Balanced Binary Search Tree, BBST），最坏的状况下，查找须要 log(2, 10^9) = 30 次 I/O 操作，且每次只能读出一个关键字（即如果这次读出来的关键字不是我要查找的，就要再进行一次 I / O 去读取数据）。如果换成 B 树，会是怎么的状况呢？
B 树是为了磁盘或其它辅助存储设备而设计的一种多叉均衡搜寻树。多级存储系统中应用 B 树，可针对内部查找，大大减少 I / O 次数。通过 B 树，可充分利用外存对批量拜访的高效反对，将此特点转化为长处。每降落一层，都以超级结点为单位（超级结点就是指一个结点内蕴含多个关键字），从磁盘中读入一组关键字。那么，具体多大为一组呢？
一个节点寄存多少数据视磁盘的数据块大小而定，比方磁盘中 1 block 的大小有 1024KB，假如每个关键字的大小为 4 Byte，则可设定每一组的大小 m = 1024 KB / 4 Byte = 256。目前，少数数据库系统采纳 m = 200~300。假如取 m = 256，则 B 树存储 1 亿条数据的树的高度大略是 log(256, 10^9) = 4，也就是单次查问所须要进行的 I / O 次数不超过 4 次，由此大大减少了 I / O 次数。
一般来说，B 树的根节点常驻于内存中，B 树的查找过程是这样的：首先，因为一个节点内蕴含多个（比方，是 256 个）关键码，所以须要先程序 / 二分来查找，如果找到则查找胜利；如果失败，则依据相应的援用从磁盘中读入下一层的节点数据（这里就波及到一次磁盘 I /O），同样的在节点内程序查找，如此往返进行…事实上，B 树查找所耗费的工夫很大一部分花在了 I / O 上，所以缩小 I / O 次数是十分重要的。
B 树的定义
B 树就是均衡的多路搜寻树，所谓的 m 阶 B 树，即 m 路均衡搜寻树。依据维基百科的定义，一棵 m 阶 B 树需满足以下要求：
- 每个结点至少含有 m 个分支节点（m>=2）。
- 除根结点之外的每个非叶结点，至多含有┌m/2┐个分支。
- 若根结点不是叶子结点，则至多有 2 个孩子。
- 一个含有 k 个孩子的非叶结点蕴含 k - 1 个关键字。（每个结点内的关键字按升序排列）
- 所有的叶子结点都呈现在同一层。实际上这些结点并不存在，能够看作是内部结点。
依据节点的分支的上上限，也能够称其为 (┌m/2┐, m) 树。比方，阶数 m = 4 时，这样的 B 树也能够称为 (2,4) 树。（事实上，(2,4)树是一棵比拟非凡的 B 树，它和红黑树有着特地的渊源！前面谈及红黑树时谈判到。）
并且，每个外部结点的关键字都作为其子树的分隔值。比方，某结点含有 2 个关键字（假如为 a1 和 a2），也就是说该结点含有 3 个子树。那么，最左子树的关键字均小于 a1；两头子树的关键字介于 a1~a2；最右子树的关键字均大于 a2。
示例，一棵 3 阶的 B 树是这个样子：
B 树的高度（理解）
假设一棵 B 树非空，具备 n 个关键字、高度为 h（令根结点为第 1 层）、阶数为 m，那么该 B 树的最大高度和最小高度别离是多少？
最大高度
当树的高度最大时，则每个结点含有的要害字数应该尽量少。依据定义，根结点至多有 2 个孩子（即 1 个关键字），除根结点之外的非叶结点至多有┌m/2┐个孩子（即┌m/2┐- 1 个关键字），为了形容不便，这里令 p = ┌m/2┐。
- 第 1 层 1 个结点（含 1 个关键字）
- 第 2 层 2 个结点（含 2 *(p-1)个关键字）
- 第 3 层 2p 个结点（含 2p*(p-1)^2 个关键字）
- …
- 第 h 层 2p^(h-2)个结点
故总的结点个数 n
≥ 1+(p-1)*[2+2p+2p^2+...+2p^(h-2)]≥ 2p^(h-1)-1
从而推导出 h ≤ log_p[(n+1)/2] + 1（其中 p 为底数，p=┌m/2┐）
最小高度
当树的高度最低时，则每个结点的关键字都至少含有 m 个孩子（即 m - 1 个关键字），则有
n ≤ (m-1)*(1 + m + m^2 +...+ m^(h-1)) = m^h - 1
从而推导出 h ≥ log_m(n+1)（其中 m 为底数）
B+ 树
B+ 树的定义
B+ 树是 B 树的一个变体，B+ 树与 B 树最大的区别在于：
- 叶子结点蕴含全副关键字以及指向相应记录的指针，而且叶结点中的关键字按大小顺序排列，相邻叶结点用指针连贯。
- 非叶结点仅存储其子树的最大（或最小）关键字，能够看成是索引。
一棵 3 阶的 B + 树示例：（好好领会和 B 树的区别，两者的关键字是一样的）
问：为什么说 B + 树比 B 树更适宜理论利用中操作系统的文件索引和数据库索引？
答：
- B+ 树更适宜内部存储。因为内结点不寄存真正的数据（只是寄存其子树的最大或最小的关键字，作为索引），一个结点能够存储更多的关键字，每个结点能索引的范畴更大更准确，也意味着 B + 树单次磁盘 IO 的信息量大于 B 树，I/ O 的次数绝对缩小。
- MySQL 是一种关系型数据库，区间拜访是常见的一种状况，B+ 树叶结点减少的链指针，增强了区间拜访性，可应用在区间查问的场景；而应用 B 树则无奈进行区间查找。
写在最初
欢送大家关注我的公众号【惊涛骇浪如码】，海量 Java 相干文章，学习材料都会在外面更新，整顿的材料也会放在外面。
感觉写的还不错的就点个赞，加个关注呗！点关注，不迷路，继续更新！！！
