最新消息:

“会思考的PHPer”主题之二:数据库索引为什么会选择B树结构

MySQL数据库 admin 1277浏览 0评论

这是一个很深的问题,我采用逐步问答的方式来解答。试图用最简洁的语言解决整体概念上的问题。

本文目的纯粹是提供对“索引采用B树结构”这个问题的一种入门概念,不涉及深入的东西。

  • 数据库索引为什么会选择B树结构?
答:因为使用B树查找时,所用的磁盘IO操作次数比平衡二叉树更少,效率也更高。
  • 为什么使用B树查找所用的磁盘IO操作次数比平衡二叉树更少?
答:大规模数据存储中,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种操作能使B树保持较低的高度,从而达到有效减少磁盘IO操作次数。
  • 什么是B树?B树有什么特征?
答:一棵度为m(也称为m阶,m为给定数)的B-树,它满足:
(1)每个结点的子结点个数≤m;

(2)根结点若不是叶子结点,它至少有两个子结点; (3)除根和叶子结点外,每个结点的子结点个数≥   ceil(m/2);(注:ceil为向上取整函数)

(4)所有的叶子结点都出现在同一层,而且不带有信息;
(5)非叶子结点若具有j+1个子结点,那么它包含j个关键字。其中,j≤m-1。B-树的非叶子结点的结构形式如下:
95b02ec534e3205de5b23f7cd152b7fa
ki (1≤i≤j)是关键字,所有关键字的值是唯一的;
pi (0≤i≤j)是指向该结点的子结点的指针。
结点中的关键字是按一定规则排好序的。假若按升序排列,有k1 < k2 < … < kj,那么,p0指向一棵关键字均小于k1的子树的根结点; pi(0<i<j)指向一棵关键字都在ki和ki+1之间的子树的根结点;pj指向一棵关键字均大于kj的子树的根结点。
8e48636b7736c8b62c9eea2897a2d96b
  • B树的查找是如何实现的?
答:在给定的m阶B树中查找一个给定值v相等的关键字,必须从根结点开始进行查找。

B树应用于文件系统的动态索引结构,这些结点存储于外部存储设备上。当一个结点从外存调入内存后,我们可就这个结点的关键字序列,使用顺序查找(m较小时),或使用二分查找( m较大时)。

      假若当前被查找的结点中有j个关键字,那么,在查找等于给定值v的关键字时,会有如下可能: (1)若v==ki (1≤i≤j),则查找成功。 (2)若v < k1  ,则 ① 如果p0为空,那么查找失败; ② 如果p0非空,那么从外存取得p0所指的结点,再继续进行查找。 (3)若ki <v< ki+1 (1≤i<j),则 ① 如果pi为空,那么查找失败; ② 如果pi非空,那么从外存取得pi所指的结点,再继续进行查找。 (4)若kj <v, 则 ① 如果pj为空,那么查找失败; ② 如果pj非空,那么从外存取得pj所指的结点,再继续进行查找。
  • 既然查找效率与树的高度紧密相关,那么B树的高度由什么决定?
答:若n≥1,m≥3,则对任意一棵具有n个关键字的m阶B树,其树高h至多为:

logt((n+1)/2)+1。 这里t是每个(除根外)内部结点的最小度数,即

B-树的高度为O(logtn)。
  • 给个B树性能分析具体例子呗?
答:首先须知:n个结点的二叉平衡的高度H(即lgn)比B树的高度h约大lgt倍,t为B树内部结点的最小度数ceil(m/2)。

【例】若阶m=1024,则lgt=lg512=9。此时若B树高度为4,则平衡的二叉排序树的高度约为36。显然,若m越大,则B树高度越小。

  • 若要作为内存中的查找表,B树的表现还要比二叉平衡树好吗?
答:非也。若要作为内存中的查找表,B树却不一定比平衡的二叉排序树好,尤其当m较大时更是如此。

因为查找等操作的CPU计算时间在B树上是 O(mlogtn)=O(lgn·(m/lgt)) 而m/lgt>1,所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此,仅在内存中使用的B树必须取较小的m。(通常取最小值m=3,此时B树中每个内部结点可以有2或3个孩子,这种3阶的B树称为2-3树)。

 

参考:

http://blog.csdn.net/v_JULY_v/article/details/6530142

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.3.2.6.htm

http://neoremind.net/2012/02/b树、b树与b树简介/

转自:http://www.wawacai.net/?p=570

转载请注明:jinglingshu的博客 » “会思考的PHPer”主题之二:数据库索引为什么会选择B树结构


Warning: Use of undefined constant PRC - assumed 'PRC' (this will throw an Error in a future version of PHP) in /usr/share/nginx/html/wp-content/themes/d8/comments.php on line 17
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址