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

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

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

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 就是基于此实现的。

原文发布于微信公众号 - 撸码那些事(lumanxs)

原文发表时间:2018-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java社区

Java开发者容易犯的十个错误

13020
来自专栏和蔼的张星的图像处理专栏

372. 在O(1)时间复杂度删除链表节点复制节点的值

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

9020
来自专栏noteless

java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

java集合框架  框架设计理念  容器 继承层级结构 继承图 集合框架中的抽象类  主要的实现类 实现类特性   集合框架分类 集合框架并发包 并发实现类

17820
来自专栏知识分享

指针--解决的疑惑

简单的就不说了,今天学链表,在链表中遇到了自己疑惑的事情,后来在网上查二级指针,搜出来一个,才解除了自己的疑惑 下面是对原文的复制,,最后有自己的链表程序--原...

32070
来自专栏菩提树下的杨过

javascript中如何正确将日期(Date)字符串转换为日期(Date)对象?

因近日一个项目中要在客户端判断用户输入的日期字符串的大小,所以对日期字符串转日期对象研究了一下,测试代码如下: <script. type="text/jav...

30480
来自专栏云霄雨霁

设计模式----迭代器模式

19200
来自专栏编程之旅

反转单向链表

单向链表的反转是一个非常常见的链表类面试题,我在刷leetcode的过程中,发现了有许多链表题目的解法,都是以反转链表为基础进行的。所以我觉得有必要记录一下。

12610
来自专栏小勇DW3

HashMap 与 ConcrrentHashMap 使用以及源码原理分析

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为...

73330
来自专栏林欣哲

HashMap解析

12730
来自专栏Android机动车

Java 基础(二)——集合源码解析 Iterator

针对一个特定的问题,如果事先不知道需要多少个对象,或者它们的持续时间有多长,那么也不知道如何保存那些对象。既然如此,怎样才能知道那些对象要求多少空间呢?事先上根...

9630

扫码关注云+社区

领取腾讯云代金券