。

下面将学习另一种树形结构B树#xff0c;这种数据结构中#xff0c;一个节点允许多余两个key的存在。

2-3树中一个节点最多能有两个key它的实现红黑树中适用对链接染色的方式去表达这两个key。

下面将学习另一种树形结构B树这种数据结构中一个节点允许多余两个key的存在。

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

1.1

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

我们选择一个参数

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

1.2

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

1.3

由于删除21后的结点的索引值个数仍然大于2Math.ceil(

5/2

从上图可知由于27是非叶子结点所以要删除27的话需要用27的后继替代它。

从上图可以看出27的后继是28因此我们用28来替代27再删除原来的28如下图

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

借是把当前结点的父节点的28下移然后把左兄弟结点的26上移到父节点删除结束。

如下图

d在上述情况接着删除32

在删除32后当前结点剩下31即索引值数目小于2。

这时候它的兄弟结点也仅仅有2个索引值所以不能向兄弟结点借。

那只能够让父结点下移一个值(30)并和兄弟结合合并成一个新的结点如下图

Math.ceil(

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

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

1.4

在我们的程序中不可避免的需要通过IO操作文件而我们的文件是存储在磁盘上的。

计算机操作磁盘上的文件是通过文件系统进行操作的在文件系统中就使用到了B树这种数据结构。

1.4.1

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

磁盘由盘片构成。

每个盘片有两面又称为盘面。

盘片中央有一个可以旋转的主轴它使得盘片以固定的旋转速率旋转通常是5400rpm或者是7200rpm一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内。

盘片的每个表面是由一个组称为磁道同心圆组成的每个磁道被划分为了一组扇区每个扇区包含相等数量的数据为通常是512字节扇区之间由一些间隙隔开这些间隙中不存储数据。

1.4.2

磁盘用磁头来读写存储在盘片表面的位而磁头连接到一个移动臂上移动臂沿着盘片半径前后移动可以将磁头定位到任何磁道上这称为寻道操作。

一旦定位到磁道后盘片转动磁道上的每个位经过磁头时读写磁头就可以感知到该位的值也可以修改值。

对磁盘的访问时间分为

由于存储介质的特性磁盘本身存取就比主存慢的多再加上机械运动耗费因此为了提高效率要尽量减少磁盘I/O减少读写操作。

为了达到这个目的磁盘往往不是严格按需读取而是每次都会预读即使只需要一个字节磁盘也会从这个为止开始顺序向后读取一定的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理

当一个数据被用到时其附近的数据也通常会马上被适用。

由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此预读可以提高I/O效率。

页是计算机管理存储器的逻辑块硬件及操作系统往往将主存和磁盘存储区分割成连续的大小相等的块每个存储块称为一页1024个字节或其整数倍预读的长度一般位页的整数倍。

主存和磁盘以页尾单位交换数据。

当程序要读取的数据不在主存中时就会触发一个缺页异常此时系统会向磁盘发出读盘信号磁盘会找到数据的起始位置并向后连续读取一页或几页数据载入内存中任何异常返回程序继续运行。

文件系统的设计者利用了磁盘预读原理将一个节点的大小设为等于一个页1024个字节或其整数倍这样每个节点只需要以此I/O就可以完全载入。

那么3层的B树可以容纳1024*1024*1024差不多10亿个数据如果换成二叉查找树则需要30层假定操作系统以此读取一个节点并且根节点保留在内存中那么B树在10亿个数据中查找目标值只需要小于3次硬盘读取就可以找到目标值但红黑树需要小于30次因此B树大大提高了IO的操作效率。

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

2.1

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

2.2

树在非叶子节点上不包含真正的数据只当作索引使用因此在内存相同的情况下能够存放更多的keyB

树的叶子节点都是相连的因此对整棵树的遍历只需要以此线性遍历叶子节点即可。

而且由于数据顺序排列并且相连所以便于区间查找和搜索。

而B树则需要进行每一层递归遍历。

2.2.2

树的每一个节点都包含key和value因此我们根据key查找value时只需要找到key所在的为止就能找到value但B

树只有叶子节点存储数据索引每一次查找都必须一次一次一直找到树的最大深度也就是叶子节点的深度才能找到value

2.3

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

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

2.3.1

18需要从第一条数据开始一直查询到第六条发现id18此时才能查询处目标结果共需要比较6次。

2.3.2

树的叶子节点形成了一个有序链表所以我们只需要找到id为12的叶子节点按照遍历链表的方式往后查询即可效率非常高

前置文章

两种数据结构的实现队列的进阶结构-优先队列2-3树思想与红黑树的实现与基本原理

ES8