由浅入深理解索引的实现

标签: mysql 索引 | 发表时间:2011-11-24 21:09 | 作者:admin
出处:http://blog.haohtml.com

00 – 背景知识

- B-Tree & B+Tree

http://en.wikipedia.org/wiki/B%2B_tree
http://en.wikipedia.org/wiki/B-tree

- 折半查找(Binary Search)

http://en.wikipedia.org/wiki/Binary_search_algorithm

- 数据库的性能问题

A. 磁盘IO性能非常低,严重的影响数据库系统的性能。
B. 磁盘顺序读写比随机读写的性能高很多。

- 数据的基本存储结构

A. 磁盘空间被划分为许多大小相同的块(Block)或者页(Page).
B. 一个表的这些数据块以链表的方式串联在一起。
C. 数据是以行(Row)为单位一行一行的存放在磁盘上的块中,如图所示.
D. 在访问数据时,一次从磁盘中读出或者写入至少一个完整的Block。

                   Fig. 1

 

01 – 数据基本操作的实现

基本操作包括:INSERT、UPDATE、DELETE、SELECT。

- SELECT

A. 定位数据
B. 读出数据所在的块,对数据加工
C. 返回数据给用户

- UPDATE、DELETE

A. 定位数据
B. 读出数据所在的块,修改数据
C. 写回磁盘

- INSERT

A. 定位数据要插入的页(如果数据需要排序)
B. 读出要插入的数据页,插入数据.
C. 写回磁盘

如何定位数据?
- 表扫描(Table Scan)

A. 从磁盘中依次读出所有的数据块,一行一行的进行数据匹配。
B. 时间复杂度 是O(n), 如果所有的数据占用了100个块。尽管只查询一行数据,
也需要读出所有100个块的数据。
C. 需要大量的磁盘IO操作,极大的影响了数据定位的性能。

因为数据定位操作是所有数据操作必须的操作,数据定位操作的效率会直接影响所有的数据操作的效率。
因此我们开始思考,如何来减少磁盘的IO?
- 减少磁盘IO

A. 减少数据占用的磁盘空间
压缩算法、优化数据存储结构
B. 减少访问数据的总量
读出或写入的数据中,有一部分是数据操作所必须的,这部分称作有效数据。剩余的
部分则不是数据操作必须的数据,称为无效数据。例如,查询姓名是‘张三’的记录。
那么这条记录是有效记录,其他记录则是无效记录。我们要努力减少无效数据的访问。

02 – 索引的产生

- 键(Key)

首先,我们发现在多数情况下,定位操作并不需要匹配整行数据。而是很规律的只匹配某一个
或几个列的值。 例如,图中第1列就可以用来确定一条记录。这些用来确定一条数据的列,统
称为 键(Key).

        Fig. 2

- Dense Index

根据减少无效数据访问的原则,我们将键的值拿过来存放到独立的块中。并且为每一个键值添
加一个指针, 指向原来的数据块。如图所示,

            Fig. 3

  这就是‘索引’的祖先 Dense Index. 当进行定位操作时,不再进行表扫描。而是进行
  索引扫描(Index Scan),依次读出所有的索引块,进行键值的匹配。当找到匹配的键值后,
根据该行的指针直接读取对应的数据块,进行操作。假设一个块中能存储100行数据,
10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据
1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储
空间换来了大约全表扫描10倍的定位效率。

03 – 索引的进化

  在实际的应用中,这样的定位效率仍然不能满足需求。很多人可能已经想到了,通过排序和查找
  算法来减少IO的访问。 因此我们开始尝试对Dense Index进行排序存储,并且期望利用排序查
  找算法来减少磁盘IO。

- 折半块查找

A. 对Dense Index排序
B. 需要一个数组按顺序存储索引块地址。以块为单位,不存储所有的行的地址。
C. 这个索引块地址数组,也要存储到磁盘上。将其单独存放在一个或多个连续的块中,如下图所示。
D. 折半查找的时间复杂度是O(logN)。在上面的列子中,dense索引总共有10,000个块。假设1个块
能存储2000个指针,需要5个块来存储这个数组。通过折半查找,我们最多只需要读取
5(数组块)+100(索引块)+1(数据块)=106个块。

                    Fig. 4

 

- Sparse Index

实现基于块的折半查找时发现,读出每个块后只需要和第一行的键值匹配,就可以决定下一个块
的位置(方向)。 因此有效数据是每个块(最后一个块除外)的第一行的数据。还是根据减少无
效数据IO的原则,将每一个块的第一行的数据单独拿出来,和索引数组的地址放到一起。这样就
可以直接在这个数组上进行折半查找了。如下图所示,这个数组就进化成了 Sparse Index

                    Fig. 5

  因为Sparse Index和Dense Index的存储结构是相同的,所以占用的空间也相同。大约需
要10个块来存储10000个Dense Index块的地址和首行键值。通过Sparse索引,仅需要读
取10(Sparse块)+1(Dense块)+1(数据块)=12个块.

- 多层Sparse Index

因为Sparse Index本身是有序的,所以可以为Sparse Index再建sparse Index。通过
这个方法,一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块
为止,如下图所示.

                   Fig. 6

  A. 这个最上层的Sparse Index称作整个索引树的根(root).
B. 每次进行定位操作时,都从根开始查找。
C. 每层索引只需要读出一个块。
D. 最底层的Dense Index或数据称作叶子(leaf).
E. 每次查找都必须要搜索到叶子节点,才能定位到数据。
F. 索引的层数称作索引树的高度(height).
G. 索引的IO性能和索引树的高度密切相关。索引树越高,磁盘IO越多。

在我们的例子中的Sparse Index,只有10个块,因此我们只需要再建立一个Sparse Index.
通过两层Sparse Index和一层Dense Index查找时,只需读取1+1+1+1=4个块。

- Dense Index和Sparse Index的区别

A. Dense Index包含所有数据的键值,但是Sparse Index仅包含部分键值。
Sparse Index占用更少的磁盘空间。
B. Dense Index指向的数据可以是无序的,但是Sparse Index的数据必须是有序的。
C. Sparse Index 可以用来做索引的索引,但是Dense Index不可以。
D. 在数据是有序的时候,Sparse Index更有效。因此Dense Index仅用于无序的数据。

- 簇索引(Clustered Index)和辅助索引(Secondary Index)

如果数据本身是基于某个Key来排序的,那么可以直接在数据上建立sparse索引,
而不需要建立一个dense索引层。 如下图所示:

Fig. 8                 Fig. 7

  这个索引就是我们常说的“ Clustered Index”,而用来排序数据的键叫做主键 Primary Key.

A. 一个表只能有一个Clustered Index,因为数据只能根据一个键排序.
B. 用其他的键来建立索引树时,必须要先建立一个dense索引层,在dense索引层上对此键的值
进行排序。这样的索引树称作 Secondary Index.
C. 一个表上可以有多个Secondary Index.

- 范围搜索(Range Search)

由于键值是有序的,因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表
的方式进行连接, 就可以实现高效的范围查找。如下图所示:

Fig. 9                Fig. 8   范围查找的过程:   A. 选择一个合适的边界值,定位该值数据所在的块   B. 然后选择合适的方向,在数据块(或Dense Index块)链中进行遍历。   C. 直到数据不满足另一个边界值,结束范围查找。 是不是看着这个索引树很眼熟?换个角度看看这个图吧!
Fig. 9

这分明就是传说中的B+Tree. - 索引上的操作   A. 插入键值   B. 删除键值   C. 分裂一个节点   D. 合并两个节点 这些操作在教科书上都有介绍,这里就不介绍了。 先写到这吧,实在写不动了,想明白容易,写明白就难了。下一篇里,打算谈谈标准B+Tree的几个问题,以及在 实现过程中,B+Tree的一些变形。 很多知识来自于下面这两本书。 “ Database Systems: The Complete Book (2nd Edition) ”
“Transaction Processing: Concepts and Techniques”

原创文章,转载请注明: 文章地址 由浅入深理解索引的实现

您可能也喜欢:

查看mysql索引使用情况

MySQL索引的索引长度问题

MySQL索引分析和优化(转)

图解"How MySQL Replication Works"
无觅

相关 [理解 索引] 推荐:

深入理解重建索引(原创)

- - ITeye博客
索引在普遍意义上能够给数据库带来带来提升,但索引的额外开销也是不容小视的,而索引的重建也是维护索引的重要工作之一. 经过维护的索引可带来以下好处:. 1、CBO对于索引的使用可能会产生一个较小的成本值,从而在执行计划中选择使用索引. 2、使用索引扫描的查询扫描的物理索引块会减少,从而提高效率. 3、于需要缓存的索引块减少了,从而让出了内存以供其他组件使用.

理解MySQL数据库覆盖索引

- - haohtml's blog
看AUTO_INCREMENT就知道数据并不多,75万条. 很简单对不对?怪异的地方在于:. 如果换成MyISAM做存储引擎的时候,查询耗时只需要0.01s,用InnoDB却会是0.15s左右. 如果只是就这么点差距其实不是什么大不了的事,但是真实的业务需求比这个复杂,造成的差距也很大:MyISAM只需要0.12s,InnoDB则需要2.2s.,最终定位到问题症结是在这条SQL.

lucene索引创建的理解思路

- - ITeye博客
虽然lucene4很早就出来,但是这里仍然以lucene3.0为基础,理解lucene索引创建的思路:. field的数据,fdx,fdt,依次写每个field的即可. 词向量,tvx,tvd,tvf. tvf是真正存储的地方,tvx是每个文档一项,具体包含第一个field的位置,其他field只要记录与覅一个field的偏移量即可.

由浅入深理解索引的实现

- - haohtml's blog
- 折半查找(Binary Search). 磁盘IO性能非常低,严重的影响数据库系统的性能. 磁盘顺序读写比随机读写的性能高很多. 磁盘空间被划分为许多大小相同的块(Block)或者页(Page). 一个表的这些数据块以链表的方式串联在一起. 数据是以行(Row)为单位一行一行的存放在磁盘上的块中,如图所示.

微软和Google如何让搜索引擎理解互联网

- - Solidot
搜索引擎爬虫抓取和索引了海量的网页内容,但内容的意义则是一无所知,它们并不能像人类那样区分同一个词的不同含义. 它们抓取的只是网页中的单词,而不是语义. 从一开始,搜索引擎本质上是匹配文本字符串. 让字符串和语义匹配起来是搜索引擎公司努力实现的方向,微软和Google正更新其搜索引擎:微软的Satori和Google的Knowledge Graph能提取出网页中的非结构性数据,创造一个互联网“名词”——人、位置、物及彼此关系——的结构性数据库.

如何理解并正确使用 MySQL 索引

- - 文章 – 伯乐在线
索引是存储引擎用于快速查找记录的一种数据结构,通过合理的使用数据库索引可以大大提高系统的访问性能,接下来主要介绍在MySql数据库中索引类型,以及如何创建出更加合理且高效的索引技巧. 注:这里主要针对的是InnoDB存储引擎的B+Tree索引数据结构. 1、大大减轻了服务器需要扫描的数据量,从而提高了数据的检索速度.

SQL Server--索引

- - CSDN博客推荐文章
         1,概念:  数据库索引是对数据表中一个或多个列的值进行排序的结构,就像一本书的目录一样,索引提供了在行中快速查询特定行的能力..             2.1优点:  1,大大加快搜索数据的速度,这是引入索引的主要原因..                             2,创建唯一性索引,保证数据库表中每一行数据的唯一性..

MongoDB 索引

- - 博客园_首页
索引是用来加快查询的,数据库索引与数据的索引类似,有了索引就不需要翻遍整本书,数据库可以直接在索引中查找,. 使得查询速度很快,在索引中找到条目后,就可以直接跳转到目标文档的位置.. 要掌握如何为查询配置最佳索引会有些难度.. MongoDB索引几乎和关系型数据库的索引一样.绝大数优化关系型数据库索引的技巧同样适用于MongoDB..

倒排索引

- - ITeye博客
倒排索引是文档检索系统中最常见的数据结构,被广泛的应用于搜索引擎. 它是一种根据内容查找文档的方式. 由于不是根据文档来找内容,而是根据进行了相反的操作,因此叫做倒排索引. 倒排索引的一个简单结构如下图所示:. 最常见的是使用词频作为权重,即单词在一个文档中出现的次数. 因此,当搜索条件为“MapReduce”“is”“simple”的时候,对应的集合为{(0.txt,1),(1.txt,1),(2.txt,2)}且{(0.txt,1),(1.txt,2)}且{(0.txt,1),(1.txt,1)}={0.txt,1.txt}.

索引原理

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