论文无忧 | 论文发表 | 手机版 | 二维码

《现代交际》杂志
本刊往期
您当前的位置:首页 杂志文章 MySQL索引背后的数据结构及算法原理
MySQL索引背后的数据结构及算法原理_杂志文章
MySQL索引背后的数据结构及算法原理
发布时间:2018-02-28浏览次数:3返回列表

李莹

(西南交通大学希望学院 四川成都610000)

[摘要]本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引、哈希索引、全文索引等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。文章主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

[关键词]数据结构 索引 算法基础

[中图分类号] TP311.1 [文献标识码]A 【文章编号】1009-5349 (2015) 08 - 0117- 01

一、索引的本质

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能地快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为0(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找( binarysearch)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

二、B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,本文暂不结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree会被如此广泛用于索引,而只是单纯从数据结构角度描述它们。

(一)B-Tree

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

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

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

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

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

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

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

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

所有节点组成树结构。

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

如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(keyl),其中v(keyl)为node的第一个[来自Www.lw5u.coM]key的值。

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

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

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。

另外,由于插入删除[来自wwW.lw5U.com]新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法。

(二)B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比,B+Tree有以下不同点:

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

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

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。

其实数据库索引调优是一项技术活,不能仅仅靠理论,因为实际情况千变万化,而且MysoL本身存在很复杂的机制,如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础,只有在明白理论的基础上,才能对调优策略进行合理推断并了解其背后的机制,然后结合实践不断实验和摸索,从而真正达到高效使用MySQL索引的目的。

责任编辑:张丽

您对《MySQL索引背后的数据结构及算法原理》一文的评论