数据库索引

什么是索引

索引就是加快检索表中数据的方法。数据库的索引类似于书籍的索引。在书籍中,索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息。在数据库中,索引也允许数据库程序迅速地找到表中的数据,而不必扫描整个数据库。

  我们通过一个简单的例子来开始教程,解释为什么我们需要数据库索引。假设我们有一个数据库表 Employee, 这个表有三个字段(列)分别是 Employee_Name、Employee_Age 和Employee_Address。假设表Employee 有上千行数据。现在假设我们要从这个表中查找出所有名字是‘Jesus’的雇员信息。我们决定使用下面的查询语句:

SELECT * FROM Employee 
WHERE Employee_Name = 'Jesus'

如果表中没有索引会发生什么?

  一旦我们运行这个查询,在查找名字为Jesus的雇员的过程中,究竟会发生什么?数据库不得不Employee表中的每一行并确定雇员的名字(Employee_Name)是否为 ‘Jesus’。由于我们想要得到每一个名字为Jesus的雇员信息,在查询到第一个符合条件的行后,不能停止查询,因为可能还有其他符合条件的行。所以,必须一行一行的查找直到最后一行-这就意味数据库不得不检查上千行数据才能找到所以名字为Jesus的雇员。这就是所谓的全表扫描。

  为如此简单的事情做全表扫描效率欠佳,数据库是不是应该更聪明一点呢?这就像用人眼从头到尾浏览整张表-很慢也不优雅(原文:not at all sleek)。此时就是索引派上用场的时候。使用索引的全部意义就是通过缩小一张表中需要查询的记录/行的数目来加快搜索的速度。

索引的分类

聚集索引:对正文内容按照一定规则排列的目录称为聚集索引。

  非聚集索引:目录自己按照一定规则排列,正文自己按照另一种规则排列,目录主要是保存对正文的一个映射关系,这种称为非聚集索引。

  以我们的汉语字典为例,我们要查一个字“爱”,我们知道它的发音,我们会自然的翻开目录中的A目录下去找读音为“ai"的字,找到它并找到它具体对应到哪一页,这里A目录下所有字具体在哪一页都是连续的,假设A目录下”爱“对应18页,在A目录中”爱”的前一个字是“矮”,对应的是17页,也就是他们在目录中的相对顺序也是他们在具体页数中的相对顺序,这个就是聚集索引

  但是如果我们遇到一个字,并不知道它的读音,我们就会采用另一种查找方式,根据“偏旁部首”去查找,然后根据这个字后的页码直接翻到某页来找到您要找的字。但你结合“部首目录”和“检字表”而查到的字的排序并不是真正的正文的排序方法,比如你查“张”字,我们可以看到在查部首之后的检字表中“张”的页码是672页,检字表中“张”的上面是“驰”字,但页码却是63页,“张”的下面是“弩”字,页面是390页,这样目录中的排列方式并不是正文实际的排列方式,这就是非聚集索引

索引采取什么数据结构存储?为什么采取这样的数据结构?

  大规模的数据不可能全部存储在内存中,故要存储到磁盘上,这样查找读取等操作时就涉及到磁盘IO,那么索引就要尽量减少磁盘IO次数,才能保证查找速度。如果采用普通的二叉查找树结构,会由于树的高度过深进行多次磁盘IO,导致查询效率低下,那么就要尽量减少树的高度,这就引出了B-TreeB+-Tree,B树B+树

  B-Tree 是最常用的用于索引的数据结构。因为它们是时间复杂度低, 查找、删除、插入操作都可以可以在对数时间内完成。另外一个重要原因存储在B-Tree中的数据是有序的。数据库管理系统(RDBMS)通常决定索引应该用哪些数据结构。但是,在某些情况下,你在创建索引时可以指定索引要使用的数据结构。

为什么使用B+树?

  1.文件很大,不可能全部存储在内存中,故要存储到磁盘上

  2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数(为什么使用B-/+Tree,还跟磁盘存取原理有关,具体看下边分析)

  3. 局部性原理与磁盘预读,预读的长度一般为页(page)的整倍数,(在许多操作系统中,页得大小通常为4k)

  4. 数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样 每个节点只需要一次I/O 就可以完全载入,(由于节点中有两个数组,所以地址连续)。而红黑树这种结构, h 明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性。

哈希表索引是怎么工作的?

  哈希表是另外一种你可能看到用作索引的数据结构,这些索引通常被称为哈希索引。使用哈希索引的原因是,在寻找值时哈希表效率极高。所以,如果使用哈希索引,对于比较字符串是否相等的查询能够极快的检索出的值。例如之前我们讨论过的这个查询(SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’) 就可以受益于创建在Employee_Name 列上的哈希索引。哈系索引的工作方式是将列的值作为索引的键值(key),和键值相对应实际的值(value)是指向该表中相应行的指针。因为哈希表基本上可以看作是关联数组,一个典型的数据项就像“Jesus => 0x28939″,而0x28939是对内存中表中包含Jesus这一行的引用。在哈系索引的中查询一个像“Jesus”这样的值,并得到对应行的在内存中的引用,明显要比扫描全表获得值为“Jesus”的行的方式快很多。

哈希索引的缺点

  哈希表是无顺序的数据结构,对于很多类型的查询语句哈希索引都无能为力。举例来说,假如你想要找出所有小于40岁的员工。你怎么使用使用哈希索引进行查询?这不可行,因为哈希表只适合查询键值对-也就是说查询相等的查询(例:like “WHERE name = ‘Jesus’)。哈希表的键值映射也暗示其键的存储是无序的。这就是为什么哈希索引通常不是数据库索引的默认数据结构-因为在作为索引的数据结构时,其不像B-Tree那么灵活。

还有什么其他类型的索引?

  使用R-Tree作为数据结构的索引通常用来为空间问题提供帮助。例如,一个查询要求“查询出所有距离我两公里之内的星巴克”,如果数据库表使用R- Tree索引,这类查询的效率将会提高。    另一种索引是位图索引(bitmap index), 这类索引适合放在包含布尔值(true 和 false)的列上,但是这些值(表示true或false的值)的许多实例-基本上都是选择性(selectivity)低的列。

索引是怎么提升性能的?

  因为索引基本上是用来存储列值的数据结构,这使查找这些列值更加快速。如果索引使用最常用的数据结构-B-Tree,那么其中的数据是有序的。有序的列值可以极大的提升性能。下面解释原因。

  假设我们在 Employee_Name这一列上创建一个B-Tree索引。这意味着当我们用之前的SQL查找姓名是‘Jesus’的雇员时,不需要再扫描全表。而是用索引查找去查找名字为‘Jesus’的雇员,因为索引已经按照按字母顺序排序。索引已经排序意味着查询一个名字会快很多,因为名字首字母为‘J’的员工都是排列在一起的。另外重要的一点是,索引同时存储了表中相应行的指针以获取其他列的数据。

数据库索引里究竟存的是什么?

  你现在已经知道数据库索引是创建在表的某列上的,并且存储了这一列的所有值。但是,需要理解的重点是数据库索引并不存储这个表中其他列(字段)的值。举例来说,如果我们在Employee_Name列创建索引,那么列Employee_Age和Employee_Address上的值并不会存储在这个索引当中。如果我们确实把其他所有字段也存储在个这个索引中,那就成了拷贝一整张表做为索引,这样会占用太大的空间而且会十分低效。

索引存储了指向表中某一行的指针

  如果我们在索引里找到某一条记录作为索引的列的值,如何才能找到这一条记录的其它值呢?这是很简单,数据库索引同时存储了指向表中的相应行的指针。指针是指一块内存区域, 该内存区域记录的是对硬盘上记录的相应行的数据的引用。因此,索引中除了存储列的值,还存储着一个指向在行数据的索引。也就是说,索引中的Employee_Name这列的某个值(或者节点)可以描述为 (“Jesus”, 0x82829),0x82829 就是包含 “Jesus”那行数据在硬盘上的地址。如果没有这个引用,你就只能访问到一个单独的值(“Jesus”),而这样没有意义,因为你不能获取这一行记录的employee的其他值-例如地址(address)和年龄(age)。

数据库怎么知道什么时候使用索引?

  当这个SQL (SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’ )运行时,数据库会检查在查询的列上是否有索引。假设Employee_Name列上确实创建了索引,数据库会接着检查使用这个索引做查询是否合理 - 因为有些场景下,使用索引比起全表扫描会更加低效。

你能强制数据库使用索引吗?

  通常来说, 你不会告诉数据库什么时候使用索引 - 数据库自己决定。然而,值得注意的是在大多数数据库中(像Oracle 和 MYSQL), 你实际上可以制订你想要使用的索引。

如何在使用SQL创建索引:

之前的例子中,在Employee_Name列上创建索引的SQL如下:

CREATE INDEX name_index
ON Employee (Employee_Name)

如何创建联合索引

我们可以在雇员表上创建两个列的联合索引,SQL如下:

CREATE INDEX name_index
ON Employee (Employee_Name, Employee_Age)

把数据库索引类比成什么比较好呢?

  一个非常好的类比是把数据库索引看作是书的索引。如果你有一本关于狗的书,你想要找关于‘黄金猎犬’的那部分。当你可以通过在书背的索引找到哪几页有关于‘黄金猎犬’信息的时候,你为什么要翻完正本书 - 这相当于数据库中的全表扫描。同样的,就像一本书的索引包含页码一样,数据库的索引包含了指针,指向你在SQL中想要查询的值所在的行。

使用数据库索引会有什么代价?

  那么,使用数据库索引有什么缺点呢?

  其一,索引会占用空间,你的表越大,索引占用的空间越大。

  其二,性能损失(主要值更新操作),当你在表中添加、删除或者更新行数据的时候, 在索引中也会有相同的操作。记住:建立在某列(或多列)索引需要保存该列最新的数据。

  基本原则是只如果表中某列在查询过程中使用的非常频繁,那就在该列上创建索引。

磁盘构造

磁盘是一个扁平的圆盘。盘面上有许多称为磁道的圆圈,数据就记录在这些磁道上。磁盘可以是单片的,也可以是由若干盘片组成的盘组,每一盘片上有两个面。如上图中所示的6片盘组为例,除去最顶端和最底端的外侧面不存储数据之外,一共有10个面可以用来保存信息

  当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头) 下通过时,就可以进行数据的读 / 写了。

  一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头,它是固定不动的,专门负责这一磁道上数据的读/写。

  活动头盘 (如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的,因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上,因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候,磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面,我们称为柱面 。因此,柱面的个数也就是盘面上的磁道数。 

磁盘的读写原理及效率

  磁盘上的数据需要使用一个三维地址来表示:柱面号盘面号块号

读/写磁盘的三个步骤:

  (1)  首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找 。

  (2)  如上图中所示的6盘组示意图中,所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。

  (3) 盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。

耗费时间:

  • 查找时间:即完成步骤(1)的时间,这部分耗时最多
  • 等待时间:即完成步骤(3)的时间
  • 传输时间:数据通过系统总线送到内存的时间

磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间。

 原文参考【https://blog.csdn.net/sinat_30186009/article/details/52169057】

    【https://blog.csdn.net/weiliangliang111/article/details/51333169】

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

MySQL索引及其实现原理(基于MyISAM及InnoDB引擎)

查询是数据库的最主要功能之一。我们都希望查询速度能尽可能快,因此数据库系统的设计者会从查询算法角度优化

2.4K10
来自专栏恰童鞋骚年

走向面试之数据库基础:二、SQL进阶之case、子查询、分页、join与视图

  假设我们有一个论坛网站,其中有一张User表{ UId,Name,Level },Level是一个int类型,代表了用户等级类型,例如:1代表骨灰,2代表大...

962
来自专栏张善友的专栏

SQL SERVER 2008 Hierarchyid数据类型

以往我们在关系数据库中建立树状结构的时候,通常使用ID+ParentID来实现两条纪录间的父子关系。但这种方式只能标示其相对位置。解决这类问题在SqlServe...

24110
来自专栏xcywt

学习SQLite之路(四)

20160621 更新 参考: http://www.runoob.com/sqlite/sqlite-tutorial.html 1. SQLite   a...

2178
来自专栏琯琯博客

Yii2 学习笔记之数据库篇

4277
来自专栏JMCui

MongoDB系列四(索引).

一、索引简介     再来老生常谈一番,什么是索引呢?数据库索引与书籍的索引类似。有了索引就不需要翻整本书,数据库可以直接在索引中查找,在索引中找到条目以后,就...

3094
来自专栏逸鹏说道

【防护】如何阻止SELECT * 语句

利用思路(仅供参考): 今天在网上看了一篇文章,是用来防止select * 的思路,其实这个可以用于安全防护的,在你出现注入的时候很多都是解猜,很多脚本小子都会...

2945
来自专栏ml

mysql知识初篇(一)

mysql介绍 (1) mysql数据库是瑞典AB开发。 (2) mysql--> sun --> oracle。 (3) mysql数据库的...

3557
来自专栏Java大联盟

Java面试手册:数据库 ⑤

1272
来自专栏Java技术栈

去 BAT 面试,总结了这 55 道 MySQL 面试题!

Mysql数据库软件是一个客户端或服务器系统,其中包括:支持各种客户端程序和库的多线程SQL服务器、不同的后端、广泛的应用程序编程接口和管理工具。

1.5K2

扫码关注云+社区

领取腾讯云代金券