b+树 多路搜索树,数据结构中树的分类

b+树 多路搜索树,数据结构中树的分类,数据结构-树(三):多路搜索树B树、B+树

本文主要介绍多通道搜索树的B树和B树,通过示例代码进行了非常详细的介绍,对大家的学习或工作有一定的参考价值。有需要的朋友下面和边肖一起学习。

多路搜索树

完全二叉树高度:O(log2N),其中2是对数

完整的m-路径搜索树的高度:O(logmN),其中m是对数,以及树的每一层的节点数。

m路径搜索树主要用于解决无法加载到内存中的数据存储问题。通过增加每层的节点数,每个节点存储更多的数据,一层可以存储更多的数据,从而降低树的高度,减少数据搜索时的磁盘访问次数。

因此,每层中的节点和每个节点中包含的关键字越多,树的高度就越短。但是确定每个节点的数据越慢,但是B树侧重于磁盘性能的瓶颈,所以单个节点搜索数据的开销可以忽略。

B树

b树是一种M路径搜索树,主要用于解决M路径搜索树不平衡导致树的高度变高的问题,就像二叉树退化为链表导致的性能问题一样。B-tree通过控制和调整每一层的节点来保证M路搜索树的平衡,比如节点分离、节点合并,以及在第一层满的时候向上分裂父节点来增加新的一层。具体规则如下:

根节点的子树个数在2到M之间,其他非叶节点的子树个数在M/2到M之间,如果因为拆分导致子树个数超过M,此时需要递归拆分父节点。当找到不需要再次分裂的父节点时,停止分裂。拆分过程到达根节点。如果根节点需要拆分,将生成两个根。因此,需要创建一个新的根,以这两个根作为子节点,树的高度将增加1。

每个非叶节点的关键字的值从左到右变大,第I个关键字代表子树i 1中最小的关键字;(其中I对于根节点在1和(2和M)之间,对于其他非叶节点在1和(M/2和M)之间);

树B的所有数据项都存储在叶节点中,非叶节点不存储数据,非叶节点只存储用于指示搜索方向的关键字,即索引。这有利于将更多的非叶节点加载到内存中,方便数据搜索;

所有叶节点深度相同,每个叶节点包含L/2到L项数据。

M和L的大小选择

是M B树的阶还是路径数。

l为每个叶节点存储的数据项的最大数量。

在B树中,每个节点都是一个磁盘块,所以M和L需要根据磁盘块的大小来确定。

磁盘区块大小与M的计算

每个非叶节点存储关键字和指向子树的指针,具体数量为M级B树。每个非叶节点存储M-1个关键字和M个指向子树的指针,所以添加的每个关键字的大小是8字节(比如Java的long类型是8字节),每个指针是4字节,所以M级B树的每个非叶节点需要8 * (m-1) 4 * m=12m。

如果规定每个非叶节点(磁盘块)占用的内存不超过8K,即8192,那么最大m为683,即683*12-8=8192。

叶子节点数据项个数L

如果每个数据项的大小也是256字节,由于磁盘块大小是8K,也就是8192字节,每个叶子节点可以存储L/2到L个数据项,所以每个叶子节点最多可以存储8192/256=32个数据项,也就是L的大小是32。

5阶B树的结构如下,即M和L等于5:其中每个非叶节点最多包含M-1=5-1=4个关键字,包括M,即5个指向子树的指针。如果l等于5,每个叶节点可以存储多达5个数据项。

B+树

B树的结构和B树基本相同。唯一不同的是,B树的叶节点通过指针连接起来,形成一个链表,这样就很容易遍历所有的叶节点,也就是获取一定范围内搜索关键词的所有数据项。MySQL的InnoDB存储引擎是以B树为索引实现的。

以上是边肖介绍的多渠道搜索树B树和B树。希望对你有帮助。如果您有任何问题,请给我留言,边肖将及时回复您。非常感谢您对我们网站的支持!

b+树 多路搜索树,数据结构中树的分类