B-Tree索引在sqlserver和mysql中的应用

标签: tree 索引 sqlserver | 发表时间:2014-11-24 07:48 | 作者:dinglang_2009
出处:http://blog.csdn.net

在谈论数据库性能优化的时候,通常都会提到“索引”,但很多人其实没有真正理解索引,并没有搞清楚索引为什么能加快检索速度,以至于在实践中并不能很好的应用索引。

事实上,索引可以说是最廉价而且十分有效一种优化手段,一般而言,设计优良的索引对查询性能优化确实能起到立竿见影的效果。


相信很多读者,都了解和使用过索引,可能也看过或者听过”新华字典“、”图书馆“之类比较通俗描述,但是对索引的存储结构和本质任然还比较迷茫。

有数据结构和算法基础的读者,应该都听过或者实践过“顺序查找,二分查找(折半)查找,二叉树查找”这几种很常见的查找算法。其中,顺序查找效率是最低的,其算法复杂度为O(n),而二分查找算法复杂度为O(logn)但要求数据是必须为有序的,通常在链表中使用广泛。而二叉树查找的复杂度仅为O(log2n),但要求数据结构为“树”。



在主流的关系型数据库中,使用和支持最广泛的要属B-Tree索引。考虑到大部分读者数据结构知识有限,为了便于理解,读者可以把B-Tree(或者其变种B+Tree)

理解为常见的二叉树。虽然这并不精确,但是相信读者看了之后,已经大致明白了为什么通过索引查找数据会比普通的表扫描会快很多。


sqlserver中的聚集索引


聚集索引的叶子节点(最底下的节点)直接包含了数据页。


sqlserver中的非聚集索引


在有聚集索引的表中,非聚集索引的叶子节点,包含的是聚集索引的键值(可以理解为聚集索引的指针)。

在没有聚集索引的堆表中,非聚集索引包含的是RID(可以理解为数据行的指针)。


在mysql中,通常也有“聚集索引”(针对InnoDB引擎)和“非聚集索引”(针对MyIsam引擎),“主键索引"和”二级索引“。

mysql InnoDB引擎中的索引结构


在主键索引中,叶子节点包含了数据行(数据页),二级索引的叶子界面,存放的是主键索引的键值(指向的主键索引)


mysql MyIsam引擎中的索引结构



主键索引与二级索引结构上没有太大的区别,叶子节点都保存的数据行信息(例如row number等)可以直接指向并定位到数据行


相信读者不难看出,B-Tree索引在sqlserver和mysql中的结构、存储方式、原理都是大致相同的。当然,也有很多细节和内部实现上的差异。


限于笔者水平和理解有限,文中全部文字和描述等全凭笔者记忆写出,难免出现错误,敬请热心的读者及时批评和指正。

由于时间有限,大部分图片笔者画的比较粗糙,也请读者谅解。


本文出自 http://blog.csdn.net/dinglang_2009,转载请注明出处。





作者:dinglang_2009 发表于2014-11-23 23:48:50 原文链接
阅读:65 评论:0 查看评论

相关 [tree 索引 sqlserver] 推荐:

B-Tree索引在sqlserver和mysql中的应用

- - CSDN博客数据库推荐文章
在谈论数据库性能优化的时候,通常都会提到“索引”,但很多人其实没有真正理解索引,并没有搞清楚索引为什么能加快检索速度,以至于在实践中并不能很好的应用索引. 事实上,索引可以说是最廉价而且十分有效一种优化手段,一般而言,设计优良的索引对查询性能优化确实能起到立竿见影的效果. 相信很多读者,都了解和使用过索引,可能也看过或者听过”新华字典“、”图书馆“之类比较通俗描述,但是对索引的存储结构和本质任然还比较迷茫.

SQLServer索引的四个高级特性

- - CSDN博客数据库推荐文章
SQLServer索引的四个高级特性. 一、Index Building Filter(索引创建时过滤).         有一些索引非常低效的,比如经常查询状态为进行中的订单,订单有99%的状态是完成,1%是进行中 ,因此我们在订单状态字段上建了一个索引,性能是提高了,但是感觉索引中保存了99%的完成状态数据是永远不会查询到的,很浪费空间.

mysql索引原理之B+/-Tree

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

B-Tree索引与Hash索引的比较

- - SegmentFault 最新的文章
B-Tree索引与Hash索引的比较. 翻译自 http://dev.mysql.com/doc/refman/5.6/en/index-btree-hash.html. 理解B-Tree和Hash的数据结构能够帮助我们预测不同存储引擎下的查询性能差异. 存储引擎在索引中使用这些数据结构,尤其是 MEMORY 同时提供了B-Tree和Hash索引让你选择.

SqlServer索引的原理与应用 - 张龙豪

- - 博客园_首页
索引的用途:我们对数据查询及处理速度已成为衡量应用系统成败的标准,而采用索引来加快数据处理速度通常是最普遍采用的优化方法. 索引是什么:数据库中的索引类似于一本书的目录,在一本书中使用目录可以快速找到你想要的信息,而不需要读完全书. 在数据库中,数据库程序使用索引可以重啊到表中的数据,而不必扫描整个表.

Oracle B-tree、位图、全文索引三大索引性能比较及优缺点汇总

- - Oracle - 数据库 - ITeye博客
引言:大家都知道“效率”是数据库中非常重要的一个指标,如何提高效率大家可能都会想起索引,但索引又这么多种,什么场合应该使用什么索引呢. 哪种索引可以提高我们的效率,哪种索引可以让我们的效率大大降低(有时还不如全表扫描性能好)下面要讲的“索引”如何成为我们的利器而不是灾难. 多说一点,由于不同索引的存储结构不同,所以应用在不同组织结构的数据上,本篇文章重点就是:理解不同的技术都适合在什么地方应用.

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) {.

oracle、mysql和sqlserver分页

- - Oracle - 数据库 - ITeye博客
sql server row number分页:. mysql limit分页:. 已有 0 人发表留言,猛击->> 这里<<-参与讨论. —软件人才免语言低担保 赴美带薪读研.

露天小便器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 的现象.