B树、B+树和B*树理论

B树、B+树和B*树理论

文章目录

​​一、B树基础知识​​​​二、B树的插入过程​​​​三、B树的删除过程​​​​四、B树的磁盘IO优势和搜索效率​​​​五、B+树理论部分​​

​​m阶B+树和m阶B树的区别​​​​B+树比B树更适合操作系统的文件索引和数据库索引的原因​​​​B树和B+树的区别​​

​​六、B*树​​

一、B树基础知识

B是Balance平衡的意思，B树的所有叶子节点都在同一层。m阶-平衡树 （一个节点有m个地址域，m-1个数据域），主要应用在文件索引系统。

AVL树：二阶平衡树。一个节点有2个地址域，1个数据域。（左右孩子的高度差是1,0，-1）

m阶B-树：最多有m个地址域（即m个孩子），m-1个数据域。除根节点和叶子节点外，其他节点的孩子至少有一半个数的孩子（指针域）（比如说有5个孩子，ceil(5/2)=3，至少有3个孩子）。

为什么说除根节点和叶子节点外，其他节点的孩子至少有一半个数的指针域？ 因为数据达到m了，节点就要进行分裂，提出一个数据成为父节点。若m是偶数，两侧数据个数分别是m/2和m/2-1，分别成为一个独立的节点，对于只有m/2-1个数据的节点来说，指针域就有m/2个，也就是ceil(m/2)

对于5阶B树来说，除根节点之外的节点的数据的个数，不能到达5，到达5的话节点就要分裂。内部节点和叶子节点范围能存储的数据范围是 [ceil(m/2)-1, m - 1]，而指针域始终比数据域多一个

二、B树的插入过程

按C、N、G、A、H、E、K、Q、M、F、W、L、T、Z、D、P、R、X、Y、S的顺序构造一棵5阶B树，详细过程如下：

分析：5阶的B树，非根节点数据个数在区间[2,4]内，每个节点最多有5个指针域，除根节点和叶子节点外，其他节点至少有2个数据，3个指针域。

对于B树来说，分裂都是向上分裂的，是非常平衡的。所有的叶子节点都在同一层，且满足搜索树的性质

三、B树的删除过程

删除以及调整的过程如下：

依次删除H、T、R、E

四、B树的磁盘IO优势和搜索效率

Windows和linux的文件搜索，以及数据库的索引，都用到了B+树结构（修改原始B树结构可得到）

在系统中的数据搜索中：大量的数据都是存储在磁盘上的。为了增加系统的搜索速度，我们一般会给数据创建索引。而所谓的创建索引，就是给数据进行排序，然后进行数据搜索就更加快速。

如果想对磁盘上存储的数据进行快速搜索查找需要解决两个问题：

更少的磁盘I/O更快的搜索速度、算法

我们在这里采用m阶平衡树（节点分裂调平衡）。红黑树不是平衡树，是二阶非平衡树。AVL树是二阶平衡树（节点旋转调平衡），左右孩子高度差不超过1。

对比AVL树以及B树的效率

操作系统管理内存都是按页面page（4K）分配，管理磁盘是按块block（16K）分配。我们的文件在磁盘存储，从磁盘读1个文件，读4个字节，实际上，操作系统从磁盘是按block（16K）来读取的。

磁盘的最小单位是扇区，一个扇区大小为512字节，一个block是16K，16K除以512就是扇区的个数。

假如现在从磁盘读取10000000个索引，构建索引树，对比B树和AVL树的花费：

如果用AVL树（相当于2阶B树）构建索引树来存储10000000个索引，需要24层。一个节点就是存储着一个索引数据，最差情况就是每个节点的数据都不在一个磁盘block上，一个节点对应一个磁盘I/O，我们查找一个数据最多查找24次，即最多需要24次磁盘I/O。

同理，使用300阶B树，查找一次数据最多找3层，花费3次磁盘I/O。

故在构建索引树的时候，我们更多的使用B树

五、B+树理论部分

磁盘上读数据，是按照block读取的。图中是3阶的，2个数据域，3个地址域，图中的数字代表索引项（例如学号作为索引）

数据都在磁盘上，花费更少的磁盘I/O才是最重要的。

我们看B树的每个节点存储的不仅仅是关键字（索引项），还存储着红色的点，这个红色的点代表索引项对应的记录，就是一行的数据。比如我们读取学号为17的数据，那就花费1次磁盘I/O；读取学号为99的数据，那就花费3次磁盘I/O。

m阶B+树和m阶B树的区别

B+树是B树的变形树

所有的叶子节点包含全部的关键字信息，及指向含有这些关键字记录的指针非叶子节点相当于是叶子节点的索引，不存储数据，叶子节点用于存储关键字以及数据索引项和数据都出现在叶子节点中，搜索每一个数据所花费的磁盘I/O都是一样的所有的叶子节点被串在一条有序的链表当中，当我们在进行区间查找的时候（where id > 1 and id < 10），我们不用遍历复杂的B+树，我们直接遍历叶子节点组成的链表即可B+树存储的索引值是有重复的，且每个节点中的关键字是有序的

B+树比B树更适合操作系统的文件索引和数据库索引的原因

B+树非叶子节点只存索引项，相对于B树就不存数据地址，所以相同大小的节点存的关键字更多，花费的磁盘I/O就少，找的就快。而且由于每个节点存储的索引多了，树的层数更低！

B树的一个节点存储了8个索引项和8个具体数据的指针地址，一共(8+8)*2=32B，需要用到两个block（磁盘块）存储一个节点。而B+树的非叶子节点只存储所索引项，而不存储具体数据的指针地址，所以B+树的一个节点16字节可以全部用来存储索引项，一个block就可以存储一个B+树的节点。

B树和B+树的区别

六、B*树

B*树是B+树的变体，在B+树的内部节点（非根和非叶子节点）再增加指向兄弟节点的指针

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。