数据库索引浅析

数据库索引的特点:

  • 避免进行数据库全表的扫描,大多数情况,只需要扫描较少的索引页和数据页,而不是查询所有数据页。而且对于非聚集索引,有时不需要访问数据页即可得到数据。
  • 聚集索引可以避免数据插入操作,集中于表的最后一个数据页面。
  • 在某些情况下,索引可以避免排序操作。

数据库索引

原文地址:http://blog.codinglabs.org/articles/theory-of-mysql-index.html

wiki:数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。

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

图片 1

index.png

为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。
但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的
索引的实现通常使用B树及其变种B 树。

数据库索引与数据结构

上文说过,二叉树、红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用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 。
  • key和指针互相间隔,节点两端是指针。
  • 一个节点中的key从左到右非递减排列。
  • 如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1),其中v(key1)为node的第一个key的值。
    如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym),其中v(keym)为node的最后一个key的值。
    如果某个指针在节点node的左右相邻key分别是keyi和keyi 1且不为null,则其指向节点的所有key小于v(keyi 1)且大于v(keyi)。
    也就是:每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。其中:
    a) Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki。
    b) Pi为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)。
    c) 关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1。

一个d=2的B-Tree示意图:

图片 2

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);

其查找节点个数的渐进复杂度为O(logd N)。

B树(Balance Tree)

又叫做B- 树(其实B-是由B-tree翻译过来,所以B-树和B树是一个概念)
,它就是一种平衡多路查找树。下图就是一个典型的B树:

graph TD
a(M)-->b(E - F)
b-->E
b-->F
a-->c(P - T - X)
E-->d(1 - 2)
F-->e(4 - 5)
B Tree

B-Tree有许多变种,其中最常见的是B Tree,例如MySQL就普遍使用B Tree实现其索引结构。
与B-Tree相比,B Tree有以下不同点:
每个节点的指针上限为2d而不是2d 1。
内节点不存储data,只存储key;叶子节点不存储指针。
一个简单的B Tree示意:

图片 3

B-Tree特点

  • 树中每个结点至多有m个孩子;
  • 除根结点和叶子结点外,其它每个结点至少有m/2个孩子;
  • 若根结点不是叶子结点,则至少有2个孩子;
  • 所有叶子结点(失败节点)都出现在同一层,叶子结点不包含任何关键字信息;
  • 所有非终端结点中包含下列信息数据 ( n, A0 , K1 , A1 , K2 , A2 , … , Kn , An ),其中: Ki (i=1,…,n)为关键字,且Ki < Ki 1 , Ai (i=0,…,n)为指向子树根结点的指针, n为关键字的个数
  • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
    B树详细定义
1. 有一个根节点,根节点只有一个记录和两个孩子或者根节点为空;
2. 每个节点记录中的key和指针相互间隔,指针指向孩子节点;
3. d是表示树的宽度,除叶子节点之外,其它每个节点有[d/2,d-1]条记录,并且些记录中的key都是从左到右按大小排列的,有[d/2 1,d]个孩子;
4. 在一个节点中,第n个子树中的所有key,小于这个节点中第n个key,大于第n-1个key,比如上图中B节点的第2个子节点E中的所有key都小于B中的第2个key 9,大于第1个key 3;
5. 所有的叶子节点必须在同一层次,也就是它们具有相同的深度;

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

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-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以查阅其它文献进行详细研究。

带有顺序访问指针的B Tree

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

图片 4

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

根据磁盘存取原理(主存存取原理不影响)、局部性原理与磁盘预读可知,一般使用磁盘I/O次数评价索引结构的优劣。
数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:
每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(logd N)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

本文由太阳集团所有网址16877发布于太阳集团城网址送彩金,转载请注明出处:数据库索引浅析

您可能还会对下面的文章感兴趣: