索引的工作原理及其种类.md at master · 0voice/interview_internal_reference · GitHub

标签: | 发表时间:2019-07-15 14:42 | 作者:
出处:https://github.com

题目:索引的工作原理及其种类

参考答案

数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。

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

为表设置索引要付出代价的:一是增加了数据库的存储空间,二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

创建索引可以大大提高系统的性能。

第一,通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。

第二,可以大大加快数据的检索速度,这也是创建索引的最主要的原因。

第三,可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。

第四,在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。

第五,通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。

也许会有人要问:增加索引有如此多的优点,为什么不对表中的每一个列创建一个索引呢?因为,增加索引也有许多不利的方面。

第一,创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

第二,索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大。

第三,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

索引是建立在数据库表中的某些列的上面。在创建索引的时候,应该考虑在哪些列上可以创建索引,在哪些列上不能创建索引。一般来说,应该在这些列上创建索引:在经常需要搜索的列上,可以加快搜索的速度;在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构;在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度;在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的;在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;在经常使用在WHERE子句中的列上面创建索引,加快条件的判断速度。

同样,对于有些列不应该创建索引。一般来说,不应该创建索引的的这些列具有下列特点:

第一,对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为,既然这些列很少使用到,因此有索引或者无索引,并不能提高查询速度。相反,由于增加了索引,反而降低了系统的维护速度和增大了空间需求。

第二,对于那些只有很少数据值的列也不应该增加索引。这是因为,由于这些列的取值很少,例如人事表的性别列,在查询的结果中,结果集的数据行占了表中数据行的很大比例,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度。

第三,对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。

第四,当修改性能远远大于检索性能时,不应该创建索引。这是因为,修改性能和检索性能是互相矛盾的。当增加索引时,会提高检索性能,但是会降低修改性能。当减少索引时,会提高修改性能,降低检索性能。因此,当修改性能远远大于检索性能时,不应该创建索引。

根据数据库的功能,可以在数据库设计器中创建三种索引:唯一索引、主键索引和聚集索引。

唯一索引

唯一索引是不允许其中任何两行具有相同索引值的索引。

当现有数据中存在重复的键值时,大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如,如果在employee表中职员的姓(lname)上创建了唯一索引,则任何两个员工都不能同姓。 主键索引 数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。 在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。 聚集索引 在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

如果某索引不是聚集索引,则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比,聚集索引通常提供更快的数据访问速度。

局部性原理与磁盘预读 由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

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

B-/+Tree索引的性能分析 到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

综上所述,用B-Tree作为索引结构效率是非常高的。

相关 [索引 工作 原理] 推荐:

解读百度搜索引擎工作原理

- - MyBlog
【文章摘要】以下便是百度搜索引擎决定搜索结果排序时考虑的六大原则,那么六大原则的侧重点是怎样的呢. 哪个原则在实际应用时占比最大呢. 在百度搜索引擎早期,这些阈值的确是相对固定的,比如“相关性”在整体排序中的重量可以占到七成. 但随着互联网的不断发展,检索技术的进步,网页数量的爆发式增长,相关性已经不是难题.

索引的工作原理及其种类.md at master · 0voice/interview_internal_reference · GitHub

- -
数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据. 索引的实现通常使用B树及其变种B+树. 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法. 为表设置索引要付出代价的:一是增加了数据库的存储空间,二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动).

索引原理

- - ITeye博客
索引是存储引擎用于快速找到记录的一种数据结构. 也就会说索引也是一种数据结构,也占用磁盘空间. 索引是对查询优化最有效的手段,可以将查询提升几个数量级,相当牛掰啊. 1)索引大大减少了服务器需要扫描的数据量. 2)索引可以帮助服务器避免排序和临时表. 3)索引可以将随机IO变为顺序IO. 数据库索引可以想象成一本书的目录,如果想在一本书中找到某个主题,那么先到书的目录中找到这个主题,然后根据目录提供的页码,找到要找的主题.

SSL工作原理

- - 互联网 - ITeye博客
SSL 是一个安全协议,它提供使用 TCP/IP 的通信应用程序间的隐私与完整性. 超文本传输协议 (HTTP)使用 SSL 来实现安全的通信. 在客户端与服务器间传输的数据是通过使用对称算法(如 DES 或 RC4)进行加密的. 公用密钥算法(通常为 RSA)是用来获得加密密钥交换和数字签名的,此算法使用服务器的SSL数字证书中的公用密钥.

CDN 工作原理

- - 互联网 - ITeye博客
1.CDN的实现基础是通过将DNS的域名设置为CNAME(就是指向另一个域名,但这个域名也是有A记录的(就是域名对应IP)). 2.CNAME的作用就是要求浏览器发送域名到CNAME这个域名的服务器去解析得到域名的IP,就是本地DNS不作IP解析,而由CNAME指定的服务器去解析. 3.CNAME指定的服务器去解析的IP地址是CDN的全局负载均衡设备IP.

oracle工作原理摘录

- - Oracle - 数据库 - ITeye博客
引自:http://blog.sina.com.cn/s/blog_79921f110100xffb.html. ORACLE工作原理1-连接. 我们从一个用户请求开始讲,ORACLE的完整的工作机制是怎样的,首先一个用户进程发出一个连接请求,如果使用的是主机命名或者是本地服务命中的主机名使用的是机器名(非IP地址),那么这个请求都会通过DNS服务器或HOST文件的服务名解析然后传送到ORACLE监听进程,监听进程接收到用户请求后会采取两种方式来处理这个用户请求,下面我们分专用服务器和共享服务器分别采用这两种方式时的情况来讲:.

Memcache工作原理总结

- - Java - 编程语言 - ITeye博客
1.  分片原理. 咱们废话话不多说了,直接看Memcache的原理. 首先memcache解决的最大的一个问题就是内存多次读取的内存碎片问题. 内存碎片分为内存内部碎片和内存外部碎片. 一般是指在外部碎片中出现了不连续的细小内存片段,不能够被进程利用.

JVM工作原理介绍

- - 开源软件 - ITeye博客
一、          JVM 的生命周期. 1.       JVM实例对应了一个独立运行的java程序它是进程级别. 启动一个Java程序时,一个JVM实例就产生了,任何一个拥有public static void main(String[] args)函数的class都可以作为JVM实例运行的起点.

mysql索引原理之B+/-Tree

- - CSDN博客架构设计推荐文章
索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree. 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子. 假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录.

数据库索引的实现原理

- - 孟飞阳的博客
说白了,索引问题就是一个查找问题. 二、数据库索引介绍及特点说明. 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据. 索引的实现通常使用B树及其变种B+树. 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法.