B树主要用来消灭M路找出树的不平衡变成树的高度

2019-11-25 15:20栏目:网络数据
TAG:

多路搜索树

B数是为了解决磁盘读取速度和CPU运算速度不匹配的问题而产生的,因为类似的动态查找树的查找速度都是和树的深度有关系的,如果数据太庞大,不可能一次性读入内存,那么必然回放入外存,于是CPU发送每一次查找指令都必须去磁盘查找,而这个过程就是相当漫长的。B数具体分为B+树,B-树,B*树。这里记录一下B+树的学习过程。一颗完全二叉树的高度大约是log2(N),然后一颗完全的M叉树的深度是logM(N),自然深度降了很多。为了避免像不平衡的二叉查找树那样退化到甚至变成一个链表,于是B+树有以下规定:

一,B-树的定义及介绍

完全二叉树高度:O,其中2为对数 完全M路搜索树的高度:O,其中M为对数,树每层的节点数 M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据,从而降低树的高度,在数据查找时减少磁盘访问次数。 所以每层的节点数和每个节点包含的关键字越多,则树的高度越矮。但是在每个节点确定数据就越慢,但是B树关注的是磁盘性能瓶颈,所以在单个节点搜索数据的开销可以忽略。

  1. 数据项存储在树叶上。
  2. 非叶节点存储M-1个关键字用来知识搜索的方向;关键字i代表下一棵子数中最小的关键字。
  3. 树的根或者一片树叶,其儿子树必须在2和M之间。
  4. 除根外,所有非树叶节点的儿子数在M/2(向上取整)和M之间。
  5. 所有树叶都在相同的深度上并且有L/2和L之间和数据项。

为什么会有B-树?

B树

这里L和M的大小确定?脑补一下,不能确定就去翻书109页。L的确定是根据磁盘的区块大小大小来确定的,比如一个区块有2000个字节,然后一个记录有10个字节,那么这个L就等于200,意思是每一个树叶节点可以保存200个记录。M大小的确定,还是比如一个区块有2000个字节,但是为了确定搜索方向必须有一些关键字,如果关键字的大小是20字节,在M阶B数中有M-1个关键字,然后还需要M个分支来指向下一个区块,每个分支占用4个字节,于是所需要的大小为20*(M-1)+4M。

熟悉的树的结构有二叉树查找树或者平衡二叉树……平衡二叉树保证最坏情况下各个操作的时间复杂度为O(logN),但是为了保持平衡,在插入或删除元素时,需要进行旋转啊...一系列操作,因此实现起来比较复杂。而对于二叉查找树,基本操作在最坏情况下会出现O(N)的时间复杂度。总之,这些树都是针对于内存中的数据操作,它们每个结点最多只有两个孩子,当数据量大时(结点数目很多),就会导致树很高。但由于基本操作(查找元素、插入元素)都是在内存中实现,因此,树高点也就没有太大的关系。

B树是一种M路搜索树,B树主要用于解决M路搜索树的不平衡导致树的高度变高,跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整,如节点分离,节点合并,一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。具体规则如下:

B数的插入

这里涉及到分裂,比如当想插入一个数时,插入到一个叶子节点,然后该叶子节点的儿子数已经达到了M这个最大值,于是不能插入,这个时候就必须进行分裂,需要将这个叶子结点分裂成2个树叶,然后就能存下了,但是分裂成了两个树叶必然会导致,父节点多出一个儿子,当父节点儿子数已经是M的时候,这个时候酒还需要分裂父节点的父节点,直到达到根节点,这个时候就需要建立一个新的根作为分好的两个儿子的父亲,这也是唯一一个增加B数高度的方式。当然还可以将当前儿子树移到相邻节点领养。具体见《算法分析与设计》111页。

试想,如果树中的结点数据 是存储在磁盘上的,每访问一个结点需要进行一次磁盘的读取操作,那么树的高度就很重要了。因为,磁盘访问的代价(速度)远远大于内存访问的代价。对于7200转的硬盘而言,访问一次磁盘大约需要8.3ms,而对于4GHz的CPU而言,8.3ms不知可以执行多少次指令了。

根节点的儿子树个数在2到M之间,其他非叶子节点的儿子树个数在M/2和M之间。如果儿子树个数因为分裂超过了M则此时需要向上递归分裂父节点,当找到一个不需要再分裂的父节点则停止分裂。该分裂过程直到根节点,如果需要分裂根节点,则会产生两个根,故需要创建一个新的根来将这两个根作为儿子节点,此时树的高度会增加1。 每个非叶子节点的关键字的值从左到右依次变大,第i个关键字代表子树i+1中的最小关键字;之间,其他非叶子节点则是1到; B树的所有数据项都存放到叶子节点,非叶子节点不存放数据,非叶子节点只存放用于指示搜索方向的关键字,即索引。这样有利于将更多的非叶子节点加载到内存中,方便进行数据查找; 所有叶子节点都在相同的深度并且每个叶子节点包含L/2到L项数据。

B数的删除

B数的删除择涉及到儿子的合并,因为父节点儿子有最少数量限制,父节点儿子数小于m/2时就需要和相临节点合并,或者从相邻节点领养一个儿子来维持自己。

因此,B树一个很重要的特征就是:高度小。

M和L的大小选择

那如何让高度变小呢?让每个结点可以拥有多个(远远大于2)孩子就可以了。但是,为了在插入、删除中仍然保持B树的性质(比如高度要低),还需要对B树做一些其他方面的规定:(实际实现过程中可能不同)。

M为B树的阶数或者说是路数 L为每个叶子节点最多存放的数据项个数 在B树中,每个节点都是一个磁盘区块,所以需要根据磁盘区块的大小来决定M和L。

其中最重要的规定是:每个结点最多包含多少个关键字(项),最少需要包含多少个关键字。

磁盘区块大小与M的计算

这里,给出一个具体的M阶 B树定义(《数据结构与算法分析》MAW著)

每个非叶子节点存放了关键字和指向儿子树的指针,具体数量为:M阶的B树,每个非叶子节点存放了M-1个关键字和M个指向儿子树的指针,故加入每个关键字的大小为8字节,每个指针为4字节,则M阶B树的每个非一叶子节点需要:8 * + 4 * M = 12M - 8个字节。 如果规定每个非叶子节点占用内存不超过8K,即8192,则M最大为683,即683*12-8=8192。

①数据项 只存储在树叶上。(数据项就是实实在在的数据,而不是索引)

叶子节点数据项个数L

②非叶子结点最多可以 存储 M-1个关键字以指示搜索的方向(这里的关键字是指索引)。

假如每个数据项大小也是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个数据项。

这里的M-1个关键字是按从小到大的顺序排序的。M-1个关键字,就有M个指针,指向进一步查找的路径。

B+树

③树的根或者是一片树叶,或者其儿子数在 2 到 M之间

B+树结构跟B树基本一致,唯一的区别是B+树的叶子节点之间通过指针相连形成一个链表,故便于遍历所有的叶子节点,即获取所有或者搜索关键字某一范围的所有数据项。MySQL的InnoDB存储引擎就是会用B+树作为索引实现。

④除根外,所有非树叶节点的儿子数在 【M/2】 和 M 之间   【M/2】表示,M/2并向上取整

以上所述是小编给大家介绍的多路搜索树B树、B+树详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持!

非叶子结点的儿子数最少为【M/2】,这就是为了保证每个结点足够多的孩子,从而使树的高度不至于太大。

⑤所有的树叶都在相同的深度上并有【L/2】 和 L 个数据项

这里表明,真正的数据只存储在叶子结点上。非叶子结点只存储索引。

 

在上面的具体规定中,M 和 L 是如何确定的呢?

M 和 L的确定与磁盘块的大小相关。对于B树而言,每个结点都尽量占据一个磁盘块。

比如,假设有 1千万数据项,每个关键字(索引)是32B,而每个数据项是256B,磁盘块的大小是8192B,如何确定M 和 L 呢?

由于M阶B树中,每个结点最多有 M-1 个关键字,故关键字总大小为 32M-32,M-1个关键字最多有M个分支指针,假设每个分支指针是4B(字节),故分支指针的大小是4*M个字节。那么对于一个非叶子结点,它的大小是36*M-32 字节,由于磁盘块大小是8192,故M = 8192/(36*M-32) = 228

(注意:这里的“关键字”其实类似于数据项,待插入的数据项 就是 通过比较关键字 来确定走哪条分支指针)

由上面的第5点可知,叶子结点只存储数据项,每个数据项大小为256B,故 L=8192/256=32,这说明每个叶子结点可以存储32个数据项。

M 与关键字以及指针的大小有关,而L与数据项的大小有关。总之,目标是:不管是叶结点还是非叶结点,都尽量保证一个结点占据一个磁盘块。

 

二,B树的基本操作

1)查找操作

查找操作的伪代码如下:《算法导论》这里的B树中数据项可存储在非叶子结点上。

 1 B-TREE-SEARCH(x,k)
 2     i = 1
 3     while i<= M' and k > key(i)
 4           i++
 5     if i<=M' and k=key(i)
 6           return (x,i)
 7     if leaf(x)
 8           return NIL
 9     else
10          DISK-READ(child(x(i)))
11          return B-TREE-SEARCH(child(x(i)),k)

x实际上代表根结点。第3行,扫描结点上所有的数据项看是否与k匹配,若不匹配且结点不是叶子结点,则需要在第10行进行一次磁盘读取操作,将该结点中某数据项指向的孩子结点读入内存,再进行比较。

2)插入操作

插入操作可能会导致结点分裂。插入操作的具体实现细节可能与这里描述的不一样。

比如,向一个已经满了的叶结点插入一个数据项时,该叶结点分裂成两个结点,并将中间数据项上移到该结点的双亲结点。

 

3)删除操作

删除操作可能会导致结点合并。具体描述参考算法导论。

比如,还可以这样来处理:当某个节点不包含的数据项已经达到最小时,可以从邻节点 “领养” 一个数据项。当邻节点也不足时,则将这两个节点合并成一个节点。

 

三,B树与B+树的主要区别

最主要的区别就是:B树中非叶子结点可以存储数据,而B+树非叶子结点只存储索引,所有的数据都放在叶子结点上存储,且所有的叶子结点到根的距离是一样的(叶子结点都在同一层)。

 

参考:B树学习总结

 

版权声明:本文由大奖888-www.88pt88.com-大奖888官网登录发布于网络数据,转载请注明出处:B树主要用来消灭M路找出树的不平衡变成树的高度