ITPub博客

首页 > Linux操作系统 > Linux操作系统 > MySQL之B-tree学习

MySQL之B-tree学习

原创 Linux操作系统 作者:541732025 时间:2013-07-30 19:48:23 0 删除 编辑


一,B tree定义:
B-树是一种平衡的多路查找树,它在文件系统中很有用,一棵m阶B树满足下列性质:
1,节点:
a,每个节点最多可以有m个子节点
b,根节点若非叶子节点,至少2个子节点,最多m个子节点
c,每个非根,非叶子节点至少[m/2]子节点或叫子树([]表示向上取整),最多m个子节点

2,关键字:
a,根节点的关键字个数1~m-1
b,非根非叶子节点的关键字个数[m/2]-1~m-1

3、所有的叶子结点都位于同一层

4、每个结点中关键字从小到大排列

5,叶子结点不包含关键字

6,性能分析:
设B-树包含N个关键字,因此有N+1个叶子结点,叶子都在第L层。因为根至少有两个孩子,因此第二层至少有2个结点。除根和叶子外,其它结点至少有┌m/2┐个孩子,因此在第三层至少有2*┌m/2┐个结点,在第四层至少有2*(┌m/2┐^2)个结点,...,在第L层至少有2*(┌m/2┐^(L-2) )个结点,于是有:
N+1 ≥ 2*┌m/2┐^(L-2)
即: L ≤ log┌m/2┐((N+1)/2 )+2
这个公式保证了B-树的查找效率是相当高的。

如果要计算数据检索时间复杂度的话,还得考虑每个节点进行关键字的查找(二分法)

一般数据库采用的是b-tree的变体:b+tree
和b-tree相比,区别在于:
1,每个节点关键字个数和子节点个数相等。
2,b+tree的每个非叶子节点只有key,没有data,而且叶子节点没有指针。
一般数据库会对b+tree进行优化,比如在叶子节点上增加了顺序访问指针,提高区间查询效率

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/28912557/viewspace-767504/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2013-05-23

  • 博文量
    127
  • 访问量
    479264