数据结构基础25：B树和B+树的区别
前言：B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种树。而事实上是，B-tree就是指的B树。数据库索引的数据结构基础就是B+树，B+树是平衡n叉排序树，属于B树的变种，通常用于数据库和操作系统的文件系统中，比B树更适合作索引的存储结构。
一、出现背景
1、索引顺序访问方法ISAM
当字典足够小，可以整个驻留在内存中时，AVL树和红黑树都能够保证良好的时间性能。对于那些必须存储在磁盘上的大型字典，就需要度数更高的搜索树来改善字典操作的性能。在研究这样的多叉搜索树前先看一下外部字典的索引顺序访问方法（indexed sequential acess method，ISAM ）：这种方法对顺序访问和随机访问都具有良好的时间性能。
索引顺序访问方法(ISAM， Indexed Sequential Access Method）：也可以称之为索引顺序存取方法，可以连续地（按照他们进入的顺序）或者任意地（根据索引）记录任何访问。每个索引定义了一次不同排列的记录。索引顺序访问文件是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道多级索引。有两种访问方法：基本的索引顺序访问方法和队列式的索引顺序访问方法。
在ISAM方法中，可用的磁盘空间被划分为很多块。块是在磁盘空间中用来输入和输出的最小单位。块一般具有和磁道一样的长度，而且可以在一次搜索或延迟中完成输入和输出。字典元素以升序存储在块中。而且这些块按照一定顺序开组织，使得从一块到另一块的延时最短。
在顺序访问时，块按序输人，每一个块中的元素按升序搜索。如果每个块包含用个元素，则搜索每个元素所需要的磁盘访问次数为1m。
要支持随机访问，就要维持一个索引。索引包括每个块的最大关键字。这样一来，索引中的关键字数量与块的数量相同，并且每个块都能储存很多元素(即m值通常较大)，因此索引足以整个驻留在内存中。为了随机访问关键字为k的元素，首先要查找索引表，确定该元素所属的块，然后把相应的块从磁盘中取出进行内部搜索，以确定该元素。结果，一次磁盘访问就足以完成次随机访问。
2、索引文件
索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段：顺序文件的键和在磁盘上相应记录的地址。存取文件中的记录需按以下步骤：
（1）整个索引文件都载入到内存中（文件很小，只占用很小的内存空间）。
（2）搜索项目，用高效的算法（如折半查询法）查找目标键。
（3）检索记录的地址。
索引文件由索引表和主文件两部分构成。
索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。
3、访问方法
基本的索引顺序访问方法 (BISAM)
在ISAM文件上检索记录时，从主索引出发，找到相应的柱面索引；从柱面索引找到记录所在柱面的磁道索引；从磁道索引找到记录所在磁道的起始地址，由此出发在该磁道上进行顺序查找，直到找到为止。若找遍该磁道均不存在此记录，则表明该文件中无此记录；若被查找的记录在溢出区，则可从磁道索引项的溢出索引项中得到溢出链表的头指针，然后对该表进行顺序查找。
为了提高检索效率，通常可让主索引常驻内存，并将柱面索引放在数据文件所占空间居中位置的柱面上，这样，从柱面索引查找到磁道索引时，磁头移动距离的平均值最小。
队列顺序访问方法(QSAM)
与 BISAM 类似，QSAM 以记录进入的顺序安排记录的存放位置，形成一个顺序数据集。但与BISAM 不同的是QSAM 由系统组织记录的成组与分解，也就是说，系统将多个记录组成块。为了提高性能，使用队列顺序访问方法往往在记录或文件在使用之前，就已经将记录或文件提前读入内存。
二、B树
B树是一种更适合于应用在外存场景的数据结构。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。B树算法减少定位记录时所经历的中间过程，从而加快存取速度。
1、B树定义
又称B-tree，B树是为了提高磁盘或外部存储设备查找效率而产生的一种平衡多路搜索树。在处理大规模数据的时候普通的数据结构不够优秀，尤其是在定位记录所经历的中间过程复杂度和区间定位上。B树可以明显的缩短定位的中间过程，加快存取速度，而且B树可以有大于2个子树的优势，可实现多路查找。
一棵M阶的B树需要满足：
（1）每个结点至多有M个孩子；
（2）除根结点和叶结点之外，其他每个结点至少有M/2个孩子；
（3）根结点至少有两个孩子（除非该树仅包含一个结点）；
（4）所有的叶结点在同一层，叶结点不包含任何关键字信息；
（5）有K个关键字的非叶结点恰好包含K+1个孩子；
注意：平衡m叉查找树是指每个关键字的左侧子树与右侧子树的高度差的绝对值不超过1的查找树，其结点结构与上面提到的B-树结点结构相同，由此可见，B-树是平衡m叉查找树，但限制更强，要求所有叶结点都在同一层。
2、B树结构图
上面的图片显示了一棵B-树，最底层的叶子结点没有显示。我们对上面提到的5条特点进行逐条解释：
1）结点的分支数等于关键字数+1，最大的分支数就是B-树的阶数，因此m阶的B-树中结点最多有m个分支，所以可以看到，上面的一棵树是一个5-阶B-树。
2）因为上面是一棵5阶B-树，所以非根非叶结点至少要有ceil(5/2)=3个分支。根结点可以不满足这个条件，图中的根结点有两个分支。
3）如果根结点中没有关键字就没有分支，此时B-树是空树，如果根结点有关键字，则其分支数比大于或等于2，因为分支数等于关键字数+1.
4）上图中除根结点外，结点中的关键字个数至少为2，因为分支数至少为3，分支数比关键字数多1，还可以看出结点内关键字都是有序的，并且在同一层中，左边结点内所有关键字均小于右边结点内的关键字，例如，第二层上的两个结点，左边结点内的关键字为15，26，他们均小于右边结点内的关键字39和45.
B-树一个很重要的特征是，下层结点内的关键字取值总是落在由上层结点关键字所划分的区间内，具体落在哪个区间内可以由指向它的指针看出。例如，第二层最左边的结点内的关键字划分了三个区间，小于15，15到26，大于26，可以看出其下层中最左边结点内的关键字都小于15，中间结点的关键字在15和26之间，右边结点的关键字大于26.
5）上图中叶子结点都在第四层上，代表查找不成功的位置。
3、B树总结
B树将更多内容放在同一个节点，对同一个节点的操作转入内存中完成，减少在外存中节点之间转移的次数，以减少磁盘操作达到提高效率的目的。
三、B +树
B+树是为数据库检索和文件检索而生的。简单的讲，B+树同B树的区别就是B+树所有的记录都在叶子节点上（B树可以把计算存在中间节点），而且B+树的所有叶子节点都通过一个指针相连。
1、B+树的定义
B+ 树是一个n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
2、B+树的性质
B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于B＋tree的性质：
1.n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
3、B＋tree结构原型图
1）说B+树查找过程之前，要先提一下磁盘IO与操作系统预读。
磁盘IO：众所周知，机械磁盘IO一次成本是很高的；
操作系统预读：操作系统的预读的时候，不仅把当前磁盘地址的数据，还把相邻的数据一起读取到内存里。
2）一个3阶B+树查找过程：
比如我们查找38。
1、 把磁盘块A读进内存，二分法查找，28<38<65，定位P2指针。
2、 通过P2指针找到磁盘块B，读进内存，35<38<56，定位指针P2。
3、 通过P2指针找到磁盘块C，读进内存，找到38。
一共就3次磁盘IO，节省资源。
注意:IO次数=B+树高度。
4、B+树相对于B树的优点
①B+树的所有Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串联起来，遍历叶子节点就能获取全部数据，这样就能进行区间访问了。
②IO一次读数据是从磁盘上读的，磁盘容量是固定的，取数据量大小是固定的，非叶子节点不存储数据，节点小，磁盘IO次数就少。
5、B+树的应用
B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。
四、为什么B+树比B树更适于索引操作？
B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B+树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
四、为什么用B+树作索引而不用红黑树等数据结构？
红黑树(自平衡二叉树)等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B+Tree作为索引结构。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。
而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。
所以，数据量较大，外存中占主要部分时，B+树因其读磁盘次数少，而具有更快的速度。
参考链接：