背景

首先，来谈谈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相干文章，学习材料都会在外面更新，整顿的材料也会放在外面。

感觉写的还不错的就点个赞，加个关注呗！点关注，不迷路，继续更新！！！