（JAVA）B树和B+树的实现原理阐述

1. B 树

2-3树中，一个节点最多能有两个key，它的实现红黑树中适用对链接染色的方式去表达这两个key。下面将学习另一种树形结构B树，这种数据结构中，一个节点允许多余两个key的存在。

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作

1.1 B 树的特性：

B树种允许一个节点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。

我们选择一个参数 M 来构造一个B树，我们可以把它称作是 M阶 的B树，那么该树具有以下特点：

• 每个节点最多右M-1个key，并且以升序排列：
• 每个节点最优能有M个子节点；
• 根节点至少有两个子节点

1.2 B树存储数据

若参数 M 选择为5，那么每个节点最多包含4个键值对，我们已5阶B树为例，看看B树的数据存储过程

1.3 B 树中删除数据

（a）原始状态

（b）在上图的树中，删除21

由于删除21后的结点的索引值个数仍然大于2（Math.ceil( 5/2 ) -1 =2），因此删除结束。

（c）接着删除27

从上图可知，由于27是非叶子结点，所以要删除27的话，需要用27的后继替代它。从上图可以看出，27的后继是28，因此我们用28来替代27，再删除原来的28，如下图：

删除后发现，当前结点(当前结点如上图所示)的索引值个数小于2个，而它的兄弟结点有3个索引值（当前结点还有一个右兄弟，选择右兄弟的话，会出现合并结点的情况，不论选哪一个都可以，只是最后的B树形态会不一样而已），那么就向左兄弟借一个索引值，注意这里的借并非直接从左兄弟结点处拿一个索引值过来，如果是这样的话，就破坏了B树父节点左子树比根结点小，右子树比根结点大的特性了。借是把当前结点的父节点的28下移，然后把左兄弟结点的26上移到父节点，删除结束。如下图：

（d）在上述情况接着删除32

在删除32后，当前结点剩下31，即索引值数目小于2。这时候，它的兄弟结点，也仅仅有2个索引值，所以不能向兄弟结点借。那只能够让父结点下移一个值(30)，并和兄弟结合合并成一个新的结点，如下图：

当前结点的索引值个数不小于2 （Math.ceil( 5/2 ) -1 =2），满足条件，删除结束。

（e）接着删除 40：

当前结点由于索引值小于2，因此需要像父结点借，父结点下移36到当前结点，然后和兄弟结点合并(选择左兄弟或右兄弟都可以，这里我选择了左兄弟)，如下图：

但这时候发现，新的当前结点的索引值个数又小于2了，那么只能向其父结点借了，所以其父结点下移33，然后当前结点和其兄弟结点合并，如下图：

删除结束。

1.4 B树在磁盘文件中的应用

在我们的程序中，不可避免的需要通过IO操作文件，而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。

1.4.1 磁盘

磁盘能够保存大量的数据，从GB一直到TB级，但是它的读取速度比较慢，因为设计到机器操作，读取速度为毫秒级。

磁盘由盘片构成。每个盘片有两面，又称为盘面。盘片中央有一个可以旋转的主轴，它使得盘片以固定的旋转速率旋转，通常是5400rpm或者是7200rpm，一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内。盘片的每个表面是由一个组称为磁道同心圆组成的，每个磁道被划分为了一组扇区，每个扇区包含相等数量的数据为，通常是512字节，扇区之间由一些间隙隔开，这些间隙中不存储数据。

1.4.2 磁盘IO

磁盘用磁头来读写存储在盘片表面的位，而磁头连接到一个移动臂上，移动臂沿着盘片半径前后移动，可以将磁头定位到任何磁道上，这称为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到该位的值，也可以修改值。对磁盘的访问时间分为 寻道时间、旋转时间以及传送时间

由于存储介质的特性，磁盘本身存取就比主存慢的多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个为止开始，顺序向后读取一定的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

• 当一个数据被用到时，其附近的数据也通常会马上被适用。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此预读可以提高I/O效率。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割成连续的大小相等的块，每个存储块称为一页（1024个字节或其整数倍），预读的长度一般位页的整数倍。主存和磁盘以页尾单位交换数据。当程序要读取的数据不在主存中时，就会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页数据载入内存中，任何异常返回，程序继续运行。

文件系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页（1024个字节或其整数倍），这样每个节点只需要以此I/O就可以完全载入。那么3层的B树可以容纳1024*1024*1024差不多10亿个数据，如果换成二叉查找树，则需要30层！假定操作系统以此读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查找目标值，只需要小于3次硬盘读取就可以找到目标值，但红黑树需要小于30次，因此B树大大提高了IO的操作效率。

2. B+树

B+树是对B树的一种变形树，它与B树的差异在于：

1. 非叶节点仅具有索引作用，也就是说，非叶子节点只存储key，不存储value；
2. 树的所有叶节点构成一个有序链表，可以按照key排序的次序遍历全部数据

2.1 B+树存储数据

若参数M选择为5那么每个节点最多包含4个键值对，我们以5阶B+树为例，看看B+树的数据存储过程

2.2 B+树和B树的对比

2.2.1 B+ 树的优点：（存储好，查找具有最坏情况）

1. 由于B+ 树在非叶子节点上不包含真正的数据，只当作索引使用，因此在内存相同的情况下，能够存放更多的key
2. B+ 树的叶子节点都是相连的，因此对整棵树的遍历只需要以此线性遍历叶子节点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层递归遍历。

2.2.2 B 树的优点：（存储比不过B+树，查找效率稳定）

由于B 树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的为止，就能找到value，但B+ 树只有叶子节点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度，也就是叶子节点的深度，才能找到value

2.3 B+ 树在数据库中的应用

在数据库的操作中，查询操作可以说时最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题，在很多数据库中，都是用到了B+树来提高查询的效率

在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。

2.3.1 为建立主键索引查询

执行select * from user where id = 18，需要从第一条数据开始，一直查询到第六条，发现id=18，此时才能查询处目标结果，共需要比较6次。

2.3.2 建立主键索引查询

2.3.3 区间查询

执行select * from user where id>=12 and id<=18，如果有了索引，由于B+ 树的叶子节点形成了一个有序链表，所以我们只需要找到id为12的叶子节点，按照遍历链表的方式往后查询即可，效率非常高

3. 前置文章

1. 浅入数据结构 “堆” - 实现和理论
2. 开始熟悉 “二叉树” 的数据结构
3. 队列 和 符号表 两种数据结构的实现
4. 队列的进阶结构-优先队列
5. 2-3树思想与红黑树的实现与基本原理

4. ES8 如何使用?

快来看看这篇好文章吧~~！！
😊👉（全篇详细讲解）ElasticSearch8.7 搭配 SpringDataElasticSearch5.1 的使用