B树概念

Catalogue
  1. 1. 背景
  2. 2. 参考文章
  3. 3. 分类
  4. 4. 前言
  5. 5. B树定义
  6. 6. B树节点定义
  7. 7. B+树
  8. 8. B*-tree
  9. 9. 总结
  10. 10. 引用

背景

mysql 使用的再多不过了,数据库索引内部实现的多数用的是B+树,但我对这个树的概念
及背后的算法,可以说是一点不了解,主要了解其定义,及算法实现。网上查了下记录如下。

参考文章

分类

  • B树(B-树)
  • B+树
  • B*树

前言

动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),
红黑树(Red-Black Tree )
,B-tree/B±tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构
其查找的时间复杂度O(log2N)与树的深度相关,那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题:就是大规模数据存储中,实现索引查询这样一个实际背景下,
树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),
这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,
进而导致查询效率低下(为什么会出现这种情况,待会在外部存储器-磁盘中有所解释),
那么如何减少树的深度(当然是不能减少查询的数据量),一个基本的想法就是:采用多叉树结构
(由于树节点元素数量是有限的,自然该节点的子树数量也就是有限的)。

也就是说,因为磁盘的操作费时费资源,如果过于频繁的多次查找势必效率低下。
那么如何提高效率,即如何避免磁盘过于频繁的多次查找呢?根据磁盘查找存取的次数往往由树的高度所决定,所以,
只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,那么是不是便能有效减少磁盘查找存取的次数呢?
那这种有效的树结构是一种怎样的树呢?

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发,自然就想到平衡多路查找树结构,
也就是这篇文章所要阐述的第一个主题B~tree,即B树结构(后面,我们将看到,B树的各种操作能使B树保持较低的高度,
从而达到有效避免磁盘过于频繁的查找存取操作,从而有效提高查找效率
)。

B树定义

B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树,与红黑树很相似。但是也存在一些不同。
B树与红黑树最大的不同在于,B树的结点可以有多个子女,从几个到上千个。
那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B树的高度也为O(lgn)
,但可能比一棵红黑树的高度小许多,因为它的分支因子比较大。所以,B树可以在O(logn)时间内,
实现各种如插入(insert),删除(delete)等动态集合操作。
(我的简单理解就是树的单层节点多了,更容易操作)

如下图所示,即是一棵B树,一棵关键字为英语中辅音字母的B树,现在要从树种查找字母R
(包含n[x]个关键字的内结点x,x有n[x]+1]个子女(也就是说,一个内结点x若含有n[x]个关键字,
那么x将含有n[x]+1个子女)。所有的叶结点都处于相同的深度,带阴影的结点为查找字母R时要检查的结点):
B树简易示意图

B树节点定义

B树节点图

B+树

B+树是应文件系统所需而产生的一种B-tree的变形树

  • 一棵m阶的B+树和m阶的B树的异同点在于:
    有n棵子树的结点中含有n-1 个关键字;
    (此处颇有争议,B+树到底是与B 树n棵子树有n-1个关键字 保持一致,还是不一致:B树n棵子树的结点中含有n个关键字,
    待后续查证。暂先提供两个参考链接:①wikipedia http://en.wikipedia.org/wiki/B%2B_tree#Overview;
    ②http://hedengcheng.com/?p=525。而下面B+树的图尚未最终确定是否有问题,请读者注意)
    所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,
    且叶子结点本身依关键字的大小自小而大的顺序链接。
    (而B 树的叶子节点并没有包括全部需要查找的信息)
    所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。
    (而B 树的非终节点也包含需要查找的有效信息)
    B+树

  • 为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?
    1)B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在
同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。
相对来说IO读写次数也就降低了。

举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。
一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。
当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

  1. B±tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。
所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

个人觉得这两个原因都不是主要原因。数据库索引采用B+树的主要原因是
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。 正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。 而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

B*-tree

B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),
B树中非根和非叶子结点再增加指向兄弟的指针;B树定义了非叶子结点关键字个数至少为(2/3)*M,
即块的最低使用率为2/3(代替B+树的1/2)。给出了一个简单实例,如下图所示:
B*-tree

总结

通过以上介绍,大致将B树,B+树,B*树总结如下:

B树:有序数组+平衡多叉树;

B+树:有序数组链表+平衡多叉树;

B*树:一棵丰满的B+树。

B+树还有一个最大的好处,方便扫库,B树必须用中序遍历的方法按序扫库,
而B+树直接从叶子结点挨个扫一遍就完了,B+树支持range-query非常方便,而B树不支持。
这是数据库选用B+树的最主要原因。

mysql 底层存储是用B+树实现的,知道为什么么。内存中B+树是没有优势的,但是一到磁盘,B+树的威力就出来了

引用

记录点滴,成为更好的自己。 — weizhuo.ma