数据库

当前位置:时时彩平台 > 数据库 > 数据库索引浅析

数据库索引浅析

来源:http://www.mrmtshipyard.com 作者:时时彩平台 时间:2019-09-28 12:39

数据库索引与数据结构

上文说过,二叉树、红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

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

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

图片 1

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

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

数据库索引的特点:

  • 避免进行数据库全表的扫描,大多数情况,只需要扫描较少的索引页和数据页,而不是查询所有数据页。而且对于非聚集索引,有时不需要访问数据页即可得到数据。
  • 聚集索引可以避免数据插入操作,集中于表的最后一个数据页面。
  • 在某些情况下,索引可以避免排序操作。
不该在以下列上创建索引
  • 对于那些在查询中很少使用或者参考的列不应该创建索引。
  • 对于那些只有很少数据值的列也不应该增加索引。
  • 对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。
  • 当修改性能远远大于检索性能时,不应该创建索引。

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

首先定义一条数据记录为一个二元组[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+Tree

其实B-Tree有许多变种,其中最常见的是B+Tree,比如MySQL就普遍使用B+Tree实现其索引结构。B-Tree相比,B+Tree有以下不同点:

  • 每个节点的指针上限为2d而不是2d+1;
  • 内节点不存储data,只存储key;
  • 叶子节点不存储指针;
  • 下面是一个简单的B+Tree示意。
graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论。

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

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

graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2
data1-->data2

如图所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。
这一节对==B-Tree和B+Tree==进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的==首选数据结构==。

缺点
  • 创建索引维护索引要耗费时间,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

两种类型的存储

在计算机系统中一般包含两种类型的存储,计算机主存(RAM)和外部存储器(如硬盘、CD、SSD等)。在设计索引算法和存储结构时,我们必须要考虑到这两种类型的存储特点。主存的读取速度快,相对于主存,外部磁盘的数据读取速率要比主从慢好几个数量级,具体它们之间的差别后面会详细介绍。 上面讲的所有查询算法都是假设数据存储在计算机主存中的,计算机主存一般比较小,实际数据库中数据都是存储到外部存储器的。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面详细介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

分类

唯一索引
唯一索引是不允许其中任何两行具有相同索引值的索引。
主键索引
数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。
在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。
聚集索引
在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

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的数学性质及插入删除算法,有兴趣的朋友可以查阅其它文献进行详细研究。

数据库索引

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

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

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

图片 3

index.png

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

创建索引的原则
  • 经常需要搜索的列上
  • 在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构
  • 经常用在连接的列上,这些列主要是一些外键
  • 在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的
  • 在经常需要排序的列上
  • 在经常使用在WHERE子句中的列上
B+Tree

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

图片 4

本文由时时彩平台发布于数据库,转载请注明出处:数据库索引浅析

关键词:

上一篇:没有了

下一篇:没有了