btree/b+tree结构原理和应用

标签: btree tree 结构 | 发表时间:2018-01-25 13:44 | 作者:张钊钊
出处:http://www.blogjava.net/
最近在公司有点时间所以深入研究了下数据库索引btree/b+tree数据结构和原理,由此牵引出了好多问题,请看如下带着问题研究。

1:为什么 btree/b+tree 数据结构适合数据库索引,它到底是怎么样一个原理和结构?

btree/b+tree 数据结构:

在之前的文章中我们介绍过AVL树,红黑树,它们都属于二叉树,即每个节点最多只能拥有2个子节点,而B-tree(B树)的每个节点可以拥有2个以上的子节点,所以我们简单概括一下:B-tree就是一颗多路平衡查找树,它广泛应用于数据库索引和文件系统中。

首先我们介绍一下一颗 m 阶B-tree的特性,那么这个 m 阶是怎么定义的呢?这里我们以一个节点能拥有的最大子节点数来表示这颗树的阶数。举个例子,如果一个节点最多有 n 个key,那么这个节点最多就会有 n+1 个子节点,这棵树就叫做 n+1(m=n+1)阶树。一颗 m 阶B-tree包括以下5条特性:

  1. 每个节点最多有 m 个子节点
  2. 除根节点和叶子节点,其它每个节点至少有 [m/2] (向上取整的意思)个子节点
  3. 若根节点不是叶子节点,则其至少有2个子节点
  4. 所有NULL节点到根节点的高度都一样
  5. 除根节点外,其它节点都包含 n 个key,其中 [m/2] -1 <= n <= m-1

这些特性可能看着不太好理解,下面我们会介绍B-tree的插入,在插入节点的过程中我们就会慢慢理解这些特性了。B-tree的插入比较简单,就是一个节点至下而上的分裂过程。下面我们具体以一颗4阶树来展示B-tree的插入过程。

首先我们 插入 200,300,400,没有什么问题,直接插入就好。

| 200 | 300 | 400 |

现在我们接着插入500,这个时候我们发现有点问题,根据定义及特性1我们知道一颗4阶B-tree的每个节点最多只能有3个key,插入500后这个节点就有4个key了。

| 200 | 300 | 400 | 500 |

这个时候我们就需要分裂,将中间的key上移到父节点,左边的作为左节点,右边的作为右节点,如下图所示:

这个时候我们是不是就明白特性3了,如果根节点不是叶子节点,那么它肯定发生了分裂,所以至少会有2个子节点。同样我们接着插入600,700,800,900插入过程如下图所示:

现在根节点也已经满了,如果我们继续插入910,920,会怎样呢?根节点就会继续分裂,树继续向上生长。看下图:

通过整个的插入过程我们也会发现,B-tree和二叉树的一个显著的区别就是,B-tree是从下往上生长,而二叉树是从上往下生长的。现在我们想想特性2和特性5是为什么?首先我们知道子节点的个数是等于key的数目+1,然后一个节点达到m个key后就会分裂,所以分裂后的节点最少能得到 m/2 - 1个key 。为啥还要减一呢?因为还要拿一个作为父节点。所以这个节点最少回拥有 m/2 - 1 + 1 = m/2 个子节点。同样得到特性5,因为最少有m/2个子节点,所以最少就含有m/2-1个key,m 阶树,每个节点存到了m个key就会分裂,所以最多就有 m-1个key。

根据以上特性我们能推出一棵含有N个总关键字数的m阶的B-tree树的最大高度h的值,

树的高度h: 1, 2, 3 , 4 ,.......... , h

节点个数s: 1, 2, 2*(m/2), 2*(m/2)(m/2), ........ ,2*(m/2)的h-2次方

s = 1 + 2(1 -  (m/2)^{h-1} )/(1- (m/2))

N = 1 + s * ((m/2) - 1) = 2 * ( (m/2)^{h-1} ) - 1

h = log┌m/2┐((N+1)/2 )+1

2:为什么btree/b+tree 为常用数据库索引结构?

上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

图5

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下:

当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

图6

一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

图7是磁盘结构的示意图。

图7

盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B- Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

综上所述,用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

dmax =  floor(pagesize / (keysize + datasize + pointsize))  (pagesize – dmax >= pointsize)

dmax =  floor(pagesize / (keysize + datasize + pointsize)) - 1  (pagesize – dmax < pointsize)

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题,下一章将讨论B+Tree是如何具体实现为MySQL中索引,同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。





张钊钊 2018-01-25 13:44 发表评论

相关 [btree tree 结构] 推荐:

btree/b+tree结构原理和应用

- - BlogJava-首页技术区
最近在公司有点时间所以深入研究了下数据库索引btree/b+tree数据结构和原理,由此牵引出了好多问题,请看如下带着问题研究. 1:为什么 btree/b+tree 数据结构适合数据库索引,它到底是怎么样一个原理和结构. btree/b+tree 数据结构:. 在之前的文章中我们介绍过AVL树,红黑树,它们都属于二叉树,即每个节点最多只能拥有2个子节点,而B-tree(B树)的每个节点可以拥有2个以上的子节点,所以我们简单概括一下:B-tree就是一颗多路平衡查找树,它广泛应用于数据库索引和文件系统中.

理解 B*tree index内部结构

- - CSDN博客数据库推荐文章
转载请注明出处: http://write.blog.csdn.net/postedit/40589651.     Oracle数据库里的B树索引就好象一棵倒长的树,它包含两种类型的数据块:一种是索引分支块,另一种是索引叶子块 索引分支块包含指向相应索引分支块/叶子块的指针和索引健值列(这里的指针是指相关分支块/叶子块的块地址RDBA.

XML to tree XML 树

- Bloger - 博客园-首页原创精华区
前面发了一个 html to tree 再发一个 xml to tree. 版权所有:版权所有(C) 2009. 文件名称:xml2tree.js. 完成日期:2009-12-22. 页:http://www.chaige.net */ var XML2Tree = function (ini) {.

mysql 索引优化 btree hash rtree

- - 数据库 - ITeye博客
mysql里目前只支持4种索引分别是:b-tree,full-text,hash以及r-tree索引. b-tree索引应该是mysql里最广泛的索引的了,除了archive,基本所有的存储引擎都支持它. 1.b-tree在myisam里的形式和innodb稍有不同. 在innodb里面有两种形态:其一是primary key形态其leafnode里存放的是数据.而且不仅存放了索引键的数据,还存放了其他字段的数据.其二是secondary index,其leafnode和普通的b-tree差不多,只是还存放了指向主键的信息.

露天小便器P-tree

- Haitao - 设计|生活|发现新鲜
2011年丹麦洛斯基尔德音乐节吸引超过10万的游客,强大的人流量对城市的公共厕所的需求也提出了考验. 但丹麦的AANDEBOOM公司却巧妙的解决了这一问题. 他们设计了50个露天小便器,分别放在主会场附近的2个不同街道. 事实证明,它确实是成功的,有大量游客乐意使用它. 这小便器还有个可爱的名字,P-Tree,向大树尿尿,顿时想到小公狗,翘起腿朝树上尿尿哦.

emacs 新手必看: undo-tree

- leafduo - LinuxTOY
火星人都知道,emacs 只有 undo ,没有 redo ……或者说它有 redo,但是相当的诡异,套用一句经典台词就是: 猥琐,非常的猥琐. 简单的说,emacs 的 redo 就是 undo undo ,也就是传说中的负负得正. 可能有些 emacs 新手,还不知道怎么去操作,因为一般情况下,无论你 undo 多少次,都不会发生 redo 的现象.

[转][转]TokuDB中的COLA-Tree和TokuMax中的Fractal tree(分形树)

- - heiyeluren的blog(黑夜路人的开源世界)
TokuDB中的COLA-Tree.       目前无论是商业的SQL Server,还是开源的MySQL,都基本上还在用比较老的 B+Tree(SQL Server用的是标准的B-Tree)的索引结构. 从原理来说,B系列树在查询过程中应该是不会慢的,而主要问题就是出现在插入. B-Tree在插入的时候,如果是最后一个node,那么速度非常快,因为是顺序写.

zTree v2.6.03 发布,JQuery Tree插件

- pathfinder - ITeye资讯频道
JQuery Tree插件zTree v2.6.03 发布了. zTree 是利用 JQuery 的核心代码,实现一套能完成大部分常用功能的 Tree 插件. 该版本修正了一些重要的bug:. 【修正】使用自定义图标功能时,异步加载无法切换为loading图标的bug. 【修正】loading 图标定义中的1像素差异,否则会导致高级异步加载中loading跳动(更新 zTreeStyle.css 和 bigDataDemo_super.html).

js Tree - 树形菜单插件

- We_Get - 博客园-首页原创精华区
      js Tree - 树形菜单.       1)DTree是 JQuery 著名树形插件Dynatree的包装类,增加右键菜单,添加、删除、更新接口.     2)jquery treeList widget 这是一个利用jQuery UI Widget Factory创建的轻量级,可换肤树形列表控件.

mysql索引原理之B+/-Tree

- - CSDN博客架构设计推荐文章
索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree. 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子. 假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录.