数据库索引背后的数据结构

栏目: 数据库 · 发布时间: 6年前

内容简介:在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。B-Tree是一种

在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

数据库索引背后的数据结构

B-Tree

B-Tree是一种 平衡 的多路**查找(又称排序)**树,在文件系统中和数据库系统中有所应用。主要用作文件的索引。 其中的B就表示平衡(Balance)

数据库索引背后的数据结构

B-Tree的特性

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

d为大于1的一个正整数,称为B-Tree的度

数据库索引背后的数据结构

h为一个正整数,称为B-Tree的高度

数据库索引背后的数据结构

key和指针互相间隔,节点两端是指针

数据库索引背后的数据结构

一个节点中的key从左到右非递减排列

数据库索引背后的数据结构

所有节点组成树结构

每个指针要么为null,要么指向另外一个节点

每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d

数据库索引背后的数据结构

每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null

数据库索引背后的数据结构

所有叶节点具有相同的深度,等于树高h

如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于key1,其中key1为node的第一个key的值

数据库索引背后的数据结构

如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于keym,其中keym为node的最后一个key的值

数据库索引背后的数据结构

如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null,则其指向节点的所有key小于keyi+1且大于keyi

数据库索引背后的数据结构

B-Tree查找数据

B-Tree是一个非常有效率的索引数据结构。这主要得益于B-Tree的度可以非常大,高度会变的非常小,只需要二分几次就可以找到数据。例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2)),检索一个key,其查找节点个数的渐进复杂度为O(logdN)。

在B-Tree中按key检索数据的算法非常直观:

  1. 首先从根节点进行二分查找,如果找到则返回对应节点的data

  2. 否则对相应区间的指针指向的节点递归进行查找,如果找到则返回对应节点的data

  3. 如果找不到,则重复过程2,直到找到节点或找到null指针,前者查找成功,后者查找失败。

B+Tree

B+Tree是B-Tree的一种变种。一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下篇文章中讨论。

数据库索引背后的数据结构

B+Tree的特性

区别于B-Tree:

每个节点的指针上限为2d而不是2d+1

内节点不存储data,只存储key;叶子节点不存储指针

带有顺序访问指针的B+Tree

一般在数据库系统或者文件系统中,并不是直接使用B+Tree作为索引数据结构的,而是在B+Tree的基础上做了优化,增加了顺序访问指针。提升了区间查询的性能。

数据库索引背后的数据结构

如上图所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。例如要查询18到30之间的数据记录,只要先找到18,然后顺着顺序访问指针就可以访问到所有的数据节点。这样就提升了区间查询的性能。数据库的 索引全扫描 index索引范围扫描 range 就是基于此实现的。

参考

MySQL索引背后的数据结构及算法原理


-----END-----

喜欢本文的朋友们,欢迎扫一扫下图关注公众号 撸码那些事 ,收看更多精彩内容

数据库索引背后的数据结构


以上所述就是小编给大家介绍的《数据库索引背后的数据结构》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

A Project Guide to UX Design

A Project Guide to UX Design

Russ Unger、Carolyn Chandler / New Riders Press / 2009-3-23 / USD 39.99

"If you are a young designer entering or contemplating entering the UX field this is a canonical book. If you are an organization that really needs to start grokking UX this book is also for you. " -......一起来看看 《A Project Guide to UX Design》 这本书的介绍吧!

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具