B树简析及其算法实现
对于B树，小编其实也不是真正的理解与掌握，花了两天总结了下有关B树的知识点，并阅读了网上的有关代码，下面是小编的一些见解，有误请批评指正。
一、大容量数据存储在磁盘
现代计算机采用分级存储的方式来实现，由内存与外存（磁盘）组成的二级存储系统中，数据全集往往存放于外存中，计算过程中则可将内存作为外存的高速缓存，存放最常用数据项的副本。借助高效的调度算法，如此便可将内存的“高速度”与外存的“大容量”结合起来。两个相邻存储级别之间的数据传输，统称I/O操作。各级存储器的访问速度相差悬殊，故应尽可能地减少I/O操作。也正因为此，在衡量相关算法的性能时，基本可以忽略对内存的访问，转而更多地关注对外存的访问次数。
二、磁盘访问
磁盘与内存一样，都是有地址的，至于为什么会有地址，那是因为组织文件的需要。不用特别了解组织文件的具体形式，只需要记得，磁盘是有存储结构的，每一个区块，都有自己的编号。具体说来，就是所在盘号（这可不是C盘D盘之类的号，而是一块物理硬盘上，具体的第几块盘片）、上下面、哪个单元，这一系列数据通过一定格式，就被定义为了磁盘地址，这个地址是真正的物理地址，而不是逻辑地址。磁盘可以被划分为不同大小的簇，一个簇可以存放几十KB到几MB不等大小的数据。
（1）索引
索引就好比是书的目录，比如当我们查看一本字典的时候，目录就相当于我们的对照表，也就是说，目录里的内容来源于书本但却独立于书本，但是呢，目录又是这本书里的一页。通过索引可以找到对应的磁盘块。
（2）访存
我们都知道，计算机的存储管理是分层的，各层次之间的速度差距比较大，尤其是辅存（磁盘）和主存之间的速度。
那么，我们都知道磁盘访问比较慢，为啥会这么慢呢？首先，cpu访问磁盘时，磁盘主要干了这些事：
① 寻道：磁头摆一摆，找到对应的柱面
② 定位：盘面转一转，磁头定位到指定扇区
在这两个步骤中，因为是机械操作，我们都晓得，这机械运动哪能比得上人家主存的电信号传播呢，所以自然就慢了不少，磁盘访问慢了，访问效率自然就跟不上了。既然这么慢，那我们肯定就得想办法，能不能在不改变这种机械运动的情况下提升一下这个访存效率呢？
这就好比你查字典，给你一个字，你翻一翻，给你一堆字，你翻n翻，查半年？能不能有个好一点的目录，一搜搜一篇，命中率嘎嘎的那种？所以，这就要求我们建立一个好的索引也就是所谓的好目录来帮助我们啦
（3）磁盘读写原理
这里主要介绍一下磁盘预读原理，在这之前，要讲一下预读原理的基础，程序的局部性原理。程序的局部性原理是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域（也就是说，这个程序在这一小段时间内只会用这一部分内存的这一小撮数据）
磁盘预读：有了这个局部性原理，那我就想了，这程序执行依次要一个数据，现在我知道它要的数据基本都是一堆一堆的凑在一起的，那我就可以在它要之前我这个磁盘先读着我这个扇区下面的内容，反正我这磁盘转着挺快的，顺序读取效率蛮高，我先读着，你要不要另说。
通过预读呢，我们就可以提前准备好要用数据，提升I/O效率。
那么我们怎么去预读呢，预读多大呢？
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
三、为何使用B树
在实际设计中，我们把一个结点设为一个页，为什么这么干呢，因为磁盘预读是以页为单位的，所以这样的话一页就代表访问一次磁盘，也就是代表一次I/O操作【比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计】。首先我们采用普通的二叉搜索树去创建这个索引，很显然它还不够好，因为二叉搜索树有可能很高，这样进行查询的复杂度还是有点大。这里要特别注意I/O复杂度这个概念，这个概念不是CPU复杂度，而是说，目前制约速度的主要因素是I/O而不是其他的。二叉树要是很高，定位一个数据就可能要一层一层地走下去，走一层就进行一次I/O，最坏的情况下磁盘IO的次数由树的高度来决定。因此要减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了。知道不好，那么能否把这棵树做平衡了呢？
B树中的每个结点根据实际情况可以包含大量的关键字信息和分支【当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右】；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据。
四、B树定义
平衡的多叉树，称为B树（B-树）。首先我们定义B树的阶：
B树中所有节点中孩子节点个数的最大值，通常用m表示（m >= 3），成为m阶B树。
我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。那么我们就不得不提一下2-3树是什么东西了，2-3树其实就是最简单的B树，每个非叶子节点都有2-3个孩子节点，所以2-3和3阶B树是同一个东西。
一颗m阶的B树定义如下：
（1）每个结点最多有m-1个关键字。
（2）根结点最少可以只有1个关键字。
（3）非根结点至少有Math.ceil(m/2)-1个关键字。【ceil为取整】
（4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
（5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
图1
上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。
图2
上图来自于网络，是用少量数据构造的一棵3叉树，实际应用中的B树结点中关键字很多的。上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针。需要注意的是：指针，关键字，以及关键字所代表的文件地址这三样东西合起来构成了B树的一个节点，这个节点存储在一个磁盘块上。这么说吧，每一个节点中的红色，是元素，黄色是地址。红色的数目不超过2，说明一个磁盘簇不能存放超过两个元素。当然实际过程中远比2要大。有了这棵树，就可以对文件进行检索。所以从中可以看到，巨型文本文件被分成了好多个簇存储在了硬盘上。而这也正是磁盘存储的实质，千万不要以为文件在光滑的盘片上是连续的一整个区段！
五、B树的插入操作
我们设定B树的阶为5。用关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}来构建一棵B树。因为树的阶为5，那么，每个节点最多有5个子节点，除了根节点，每个节点内的关键字个数大于等于2。
自上而下查找插入叶结点位置；
自下而上分裂满结点
1、插入1，得到下图：
图3
2、接着继续插入2、6、7，得到下图：
图4
3、接下来插入11，得到下图：
图5
插入后超过了最大允许的关键字个数4，所以以key值为6为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。
图6
4、插入4，8，13得到下图：
图7
5、插入11，得到下图：
图8
因为最右下的节点内有5个元素，超过最大个数4了，所以需要进行拆分，把中间节点10进行提升，上升到和6一起，形成如下结构：
图9
6、然后插入5，17，9，16，得到如下：
图10
7、插入20，得到下图：
图11
分裂，得到下图：
图12
8、之后插入3、12、14、18、19，后，形成如下结构：
图13
9、然后插入15，会导致13提升到根节点，这时，根节点会有5个节点，那么，根节点中的10会再次进行提升，形成如下结构：
图14
六、B树的删除操作
删除操作比较复杂，主要是因为删除的项可能在叶子节点上也可能在非叶子节点上，而且删除后可能导致不符合B树的规定，这里暂且称之为导致B树不平衡，于是要进行一些合并、左旋、右旋等操作，使之符合B树的规定（即让B树平衡）。另外，如果是删除非叶子节点项需要先找到中序前驱来替换。删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。
（1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
（2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
（3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。
（4）否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
（5）有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可
【这里以5阶的B树为例子来分析，5阶的B树除了根节点，叶子节点的关键字个数要大于等于2】
（1）要删除的项在叶子节点上且不影响B树的平衡结构
图15
在上面的B树中删除9，从根节点开始查找，小于10，往左分支查找，最后可找到9，删除后结点中的关键字个数仍然等于2，所以删除结束。得到下图：
图16
（2）要删除的项在叶子节点上，删除后打破平衡需要从右兄弟节点中借项，而且右兄弟节点有足够的项借给它
在上面的B树中删除15。发现此时发现节点15的右兄弟节点有项可以借给它，于是删除15，然后进行左旋操作，左旋即原来的父节点16下移到左子节点填补原来的节点15，右子节点中最小值的项17提升到父节点，最终如下：
图17
（3）要删除的项在叶子节点上，删除后打破平衡需要从左兄弟节点中借项，而且左兄弟节点有足够的项借给它。【上图不存在这种情况，这里不做展示】
（4）要删除的项在非叶子节点上
在上面的B树中删除17，从上图可知17位于非叶子结点中，所以用17的后继替换它。从图中可以看出，17的后继为18，我们用18替换17，然后在18（原17）的右孩子结点中删除18。删除后的结果如下图所示。
图18
由于删除后的叶子结点的记录的等于2，不用继续调整。否则继续进行相应调整。
（5）要删除的项在叶子节点上，删除后打破平衡，而且左右兄弟节点都没有项可以借给它。
在上面的B树中删除5，同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。得到下图：
图19
发现6所处节点关键字少于2，因此需要进行合并操作，得到下图：
图20
合并后结点满足条件，删除结束。
七、B树实现代码
下面是小编在网上找到并修改的代码，并创建了一棵6阶B树，截图如下：
图21
图22
八、参考
（1）https://www.cnblogs.com/nullzx/p/8729425.html
（2）https://blog.csdn.net/chengweiuser/article/details/76522244
