数据库中的索引有什么用(索引功能介绍及应用大全)

数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),然而这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。作为一种数据结构,索引专为加快查找速度而设计。索引本质上就是把一个关键字与它对应的记录相关联的过程,一个索引由若干个索引项组成,每个索引至少包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

PartⅠ 索引数据结构

索引主要分为线性索引、树形索引和多级索引。下面将简单介绍一些基础的索引实现方式以引出MySQL的索引实现。

1.1 线性索引所谓线性索引就是将索引项集合组织为线性结构,也成为索引表。虽然MySQL常使用树形索引,但是线性索引的有些性质和树形索引是相通的,所以先简单介绍一下两种比较常见的线性索引。1.1.1 稠密索引稠密索引在线性索引中,将数据记得每一条记录都对应一个索引项,并维护一个索引表。由于在真实环境中可能需要应对大量的数据,所以对于稠密索引的索引表来说,索引项一定是按照关键码有序的排列。

数据库中的索引有什么用(索引功能介绍及应用大全)索引项有序就意味着可以直接对索引表进行像二分查找、插值查找、斐波那契查找等高效率的查找操作,大大减少查询的时间复杂度。但是稠密索引也有一个明显的缺点,对于大量数据状态下索引表会变得非常的长,如果全部取出内存的话将会占用大量内存空间。1.1.2 分块索引为了解决稠密索引带来的问题于是就有了分块索引。分块索引是稀疏索引的一种,把数据记得记录分成了若干块,,实现了分块有序,这些块满足以下两个条件:第一个是块间有序,例如要求第二块所有记录的索引关键字均大于第一块中所有的记录关键字,第三块要大于第二块的。第二个是块内无序,块内的记录可以瞎排虽然可以实现块内有序,但是这就造成了和稠密索引一样的问题。对于分块有序的数据将每块建立一个索引项,这种索引方法叫做分块索引。分块索引的索引项结构可以如下:最大关键字,用于存储每一块的最大关键字,可作为这一块所有数据的关键字范围的依据;块记录个数,方便遍历块数据;用于指向块首数据的指针,用于遍历块。使用分块索引,即使是遍历索引列表再遍历对应的块,也要比直接遍历全部数据效率高,而且对于有序的索引列表还可以使用更高效的查找算法。总的来说,对细分快不需要有序的情况下,分块索引兼顾了空间效率和时间效率,大大增加了整体查找的速度,所以也被普遍运用于数据库表的查找技术应用中。1.2树形索引1.2.1 二叉树、平衡二叉树和红黑树索引

线性索引在插入和删除上就要浪费大量的时间,这点对于数据量大的情况下尤为明显。所以MySQL的引擎几乎没有使用线性索引。MySQL的主流存储引擎都使用B-/B 树索引,作为二叉树的变种,我们先简单介绍一下使用二叉搜索树构建的索引。二叉搜索树(binary search tree)又称为二叉查找树,它或者是一棵空树,要么是具有以下性质的二叉树:若该树左子树不为空,则左子树上所有节点值均小于其根节点;若该树右子树不为空,则右子树上所有节点值均大于其根节点;该树的左右子树也是二叉搜索树。一个可能的二叉树索引如下:

二叉树在保留了二分搜索的前提下,使插入和删除上可以直接修改指针实现,极大提高插入和删除的效率。但是由于二叉树的形状不确定性导致极端查询时间复杂度和平均查询时间复杂度相差很大。例如如果插入数据时本身就是从小到大插入的,那么在构建索引时就会构建出一条极右斜树,他虽然是二叉搜索树,但是这时候对索引的搜索效率等于遍历效率,即O(n),而对于上图情况却最多只需要查找两次。所以就有了平衡二叉树(AVL tree)和红黑树(Red–black tree)平衡二叉树上所有结点的平衡因子(balance factor)值只能是-1、0、1,保证了查找时的效率问题,但是同样的由于频繁调整树的节点,插入和删除效率下降。而红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构,能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。1.3B-/B 树索引B树(B-树)是为了磁盘或其它存储设备而设计的一种多路平衡查找树,其本质就是使用[key, balue]结构构建出查找路线,key为记录的键值(即索引值),value对应不同数据记录。可以使用度和阶来定义B树。这里使用阶来定义:节点最大的孩子书目称为B树的阶。一个m阶的B树具有如下性质:如果根节点不是叶子节点,则其最少有两棵子树;设(m/2) ≤ k ≤ m,则每个根的分支节点都有k-1个元素和k个孩子,每个叶子节点n都有k-1个元素;所有叶子节点深度相同且等于树高h;每个非终端结点中包含有n个关键字信息:(n,P0,K1,P1,K2,P2,……,Kn,Pn)。其中:Ki(i=1…n)为关键字,且关键字按顺序升序排序K(i-1) < KiPi为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)关键字的个数n必须满足(m/2)-1 <= n <= m-1一个示例B树结构:

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。伪代码参考如下:BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i 1]->node);}data = BTree_Search(root, my_key);关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N 1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。B树与红黑树最大的不同在于,B树的结点可以有许多子女,从几个到几千个。与红黑树一样,一棵含n个结点的B树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,因为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。B树解决了树深问题,但如果每个节点在磁盘的不同页,B树还是需要在硬盘的页面进行多次访问才能遍历所有元素, 为了解决这个问题就有了B 树,与B-Tree相比,B Tree有以下不同点:每个节点的指针上限为2d而不是2d 1;分支节点类似索引key,只存储其子树中最大或者最小的节点;叶子节点包含全部关键字信息及指向其的指针;出现在分支节点的元素会被追加到该分支节点位置的中序后继者中。

一般在数据库系统或文件系统中使用的B Tree结构都在经典B Tree的基础上进行了优化,增加了顺序访问指针,如下图。

所以要遍历的时候直接使用链表,要查找的时候从树根查找。B 树的结构特别适合带有范围的查找,可以从根节点找到范围左边界的数据,然后再遍历到右边界即可。

PartⅡ MySQL中的B-TREE索引

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B Tree,非单调的主键会造成在插入新记录时数据文件为了维持B Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。2.3为什么使用B-/B 树我们上面提到的所有索引数据结构,除了分块索引以外,其他的索引查找,都需要把所有的数据行都建立索引,索引索引本身会特别大,不可能全部存储在内存中。因此索引一般是以文件的形式存储在硬盘里。2.3.1 主存存取计算机的主存基本都是随机访问存储器(Random-Access Memory,RAM),其分为两类:静态随机访问存储器(SRAM)和动态随机访问存储器(DRAM)。SRAM比DRAM快,但是也贵的多,一般作为CPU的高速缓存,DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂,基本是使用电信号来保存信息的,不存在机器操作,所以访问速度非常快。他们是易失的,即如果断电,保存DRAM和SRAM保存的信息就会丢失。2.3.2 磁盘存取磁盘空间动辄百GB级的容量以及低廉的价格使得磁盘成为数据的主要存储区,但是磁盘存取相对于主存来说却多了一些额外的步骤导致效率远不如直接读写主存。因为磁盘涉及到机器操作,读取速度一般为毫秒级,从DRAM读速度比从磁盘度快10万倍,从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构以分析磁盘读写原理。

PartⅢ散列表查找(哈希查找)

11B/B 树作为索引,所有只会访问或者修改一条数据的 SQL 的时间复杂度都是O(log n)。也就是树的高度,但是使用哈希却有可能达到 O(1) 的时间复杂度,看起来散列表查找效率特别美好。但是如果我们使用哈希作为底层的数据结构,遇到order by、大于小于、更新索引列的值等场景时,使用哈希构成的主键索引或者辅助索引可能就没有办法快速处理了。散列表对于处理范围查询或者排序性能会非常差,只能进行全表扫描并依次判断是否满足条件,也就意味着我们使用的索引对于这些查询没有其他任何效果,最终的性能可能都不如从日志中顺序进行匹配。另外散列表的存储是尽量将数据打散到一个区间,打散的存储对于磁盘读写来说也是非常的不友好。因此对于MySQL的Innodb,只有少量读取请求会使用散列表优化读取速度,大部分情况,还是使用B 树。

↓↓更多惊喜优惠请点这儿~

发表评论

登录后才能评论