数据库索引分析

 

从下列几种情况下查找某一个汉字：

1. 一堆汉字
2. 有拼音目录的字典
3. 有部首目录的字典

解决的方案：

1. 一个一个找，直接找到为止
2. 按照拼音表的顺序找，拼音表是有序的，字在字典中也是有序的，很容易找。
3. 根据部首目录来找，先找部首，再找汉字。汉字在字典中是无序的。

加一个汉字，会怎么样，大家可以先想想看。

 

其实这各结构和数据搜索是很类似的：

1. 全表扫描直到找到为止
2. 用聚集索引查找
3. 用非聚集索引查找

• 索引

 

     在数据库中，索引的含义与日常意义上的“索引”一词并无多大区别（想想小时候查字典），它是用于提高数据库表数据访问速度的数据库对象。
A ）索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页，而不是遍历所有数据页。
B ） 对于非聚集索引，有些查询甚至可以不访问数据页。
C ） 聚集索引可以避免数据插入操作集中于表的最后一个数据页。
D ） 一些情况下，索引还可用于避免排序操作。

 

当然，众所周知，虽然索引可以提高查询速度，但是它们也会导致数据库系统更新数据的性能下降，因为大部分数据更新需要同时更新索引

• 聚集索引

    表数据按照索引的顺序来存储的。自然界的事物都是按照某一种顺序排列的，当然它只能有一种顺序。所以数据表中的聚集索引只能建立一次。对于聚集索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。下面会具体介绍。

• 非聚集索引

    表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，该层紧邻数据页，其行数量与数据表行数据量一致。

 

先来看一下索引存储的一个简单的结构，一条索引记录中包含的基本信息包括：键值（即你定义索引时指定的所有字段的值）+逻辑指针（指向数据页或者另一索引页）;

 

 

 

当你为一张空表创建索引时，数据库系统将为你分配一个索引页，该索引页在你插入数据前一直是空的。此页此时既是根结点，也是叶结点。每当你往表中插入一行数据，数据库系统即向此根结点中插入一行索引记录。当根结点满时，数据库系统大抵按以下步骤进行分裂：
A ）创建两个儿子结点
B ）将原根结点中的数据近似地拆成两半，分别写入新的两个儿子结点
C ）根结点中加上指向两个儿子结点的指针

 

通常状况下，由于索引记录仅包含索引字段值（以及 4-9 字节的指针），索引实体比真实的数据行要小许多，索引页相较数据页来说要密集许多。一个索引页可以存储数量更多的索引记录，这意味着在索引中查找时在 I/O 上占很大的优势，理解这一点有助于从本质上了解使用索引的优势。

 

 

索引的查找，类似Btree的方式

 

 

 

但Btree有几个问题：

1. 左右树的树高不一样，如果查询的索引大部份都在树高的一边，那查询的效率就会偏低了
2. 在非叶子节点也可以命中，当索引更新时，会产生极大的消耗。

由于以下的问题，不同的数据对索引存储实现不完全使用Btree,而是经过一个改变。

 

 我们常见的数据库系统，其索引使用的数据结构多是B-Tree或者B+Tree。
 MySql, Berkerly DB使用的是B+Tree
 Oracle及Sysbase使用的是B-Tree。

 

B+tree的结构：

 

B+tree比Btree在性能方面有了很大的提升。

 

1. B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
2. 因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3. B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。

 

• 聚集索引

在聚集索引中，叶结点也即数据结点，所有数据行的存储顺序与索引的存储顺序一致。

 

 

 

1 ）聚集索引与查询操作

如上图，我们在名字字段上建立聚集索引，当需要在根据 此字段 查找特定的记录时，数据库系统会根据 特定的系统表 查找的此索引的根，然后根据指针查找下一个，直到找到。例如我们要查询“ Green ”，由于 它介于[Bennet, Karsen] ，据此我们找到了索引页 1007 ，在该页中 “Green” 介于 [Greane , Hunter] 间 ，据此我们找到叶结点 1133 （也即数据结点），并最终在此页中找以了目标数据行。

 

此次查询的 IO 包括 3 个索引页的查询（其中最后一次实际上是在数据页中查询）。这里的查找可能是从磁盘读取 (Physical Read) 或是从缓存中读取 (Logical Read) ，如果此表访问频率较高，那么索引树中较高层的索引很可能在缓存中被找到。所以真正的 IO 可能小于上面的情况。

 

 

2 ）聚集索引与插入操作

最简单的情况下，插入操作根据索引找到对应的数据页，然后通过挪动已有的记录为新数据腾出空间，最后插入数据。

 

如果数据页已满，则需要拆分数据页（页拆分是一种耗费资源的操作，一般数据库系统中会有相应的机制要尽量减少页拆分的次数，通常是通过为每页预留空间来实现）：
A ） 在该使用的数据段（ extent ）上分配新的数据页，如果数据段已满，则需要分配新段。
B ） 调整索引指针，这需要将相应的索引页读入内存并加锁。
C ） 大约有一半的数据行被归入新的数据页中。
D ） 如果表还有非聚集索引，则需要更新这些索引指向新的数据页。

 

特殊情况：
A ） 如果新插入的一条记录包含很大的数据，可能会分配两个新数据页，其中之一用来存储新记录，另一存储从原页中拆分出来的数据。
B ） 通常数据库系统中会将重复的数据记录存储于相同的页中。
C ） 类似于自增列为聚集索引的，数据库系统可能并不拆分数据页，页只是简单的新添数据页。

 

 

3 ）聚集索引与删除操作

删除行将导致其下方的数据行向上移动以填充删除记录造成的空白。

如果删除的行是该数据页中的最后一行，那么该数据页将被回收，相应的索引页中的记录将被删除。如果回收的数据页位于跟该表的其它数据页相同的段上，那么它可能在随后的时间内被利用。如果该数据页是该段的唯一一个数据页，则该段也被回收。

 

对于数据的删除操作，可能导致索引页中仅有一条记录，这时，该记录可能会被移至邻近的索引页中，原索引页将被回收，即所谓的“索引合并”。

 

• 非聚集索引

 

非聚集索引与聚集索引相比：
A ） 叶子结点并非数据结点
B ） 叶子结点为每一真正的数据行存储一个 “ 键 - 指针 ” 对
C ） 叶子结点中还存储了一个指针偏移量，根据页指针及指针偏移量可以定位到具体的数据行。
D ） 类似的，在除叶结点外的其它索引结点，存储的也是类似的内容，只不过它是指向下一级的索引页的。

 

聚集索引是一种稀疏索引，数据页上一级的索引页存储的是页指针，而不是行指针。而对于非聚集索引，则是密集索引，在数据页的上一级索引页它为每一个数据行存储一条索引记录。

 

对于根与中间级的索引记录，它的结构包括：
A ） 索引字段值
B ） RowId （即对应数据页的页指针 + 指针偏移量）。在高层的索引页中包含 RowId 是为了当索引允许重复值时，当更改数据时精确定位数据行。
C ） 下一级索引页的指针

 

对于叶子层的索引对象，它的结构包括：
A ） 索引字段值
B ） RowId

 

 

1 ）非聚集索引与查询操作

针对上图，如果我们同样查找“ Green ”，那么一次查询操作将包含以下 IO ： 3 个索引页的读取 +1 个数据页的读取。 同样，由于缓存的关系，真实的 IO 实际可能要小于上面列出的。

 

 

2 ）非聚集索引与插入操作

如果一张表包含一个非聚集索引但没有聚集索引，则新的数据将被插入到最末一个数据页中，然后非聚集索引将被更新。如果也包含聚集索引，该聚集索引将被用于查找新行将要处于什么位置，随后，聚集索引、以及非聚集索引将被更新。

 

 

3 ）非聚集索引与删除操作

如果在 删除命令的 Where 子句中包含的列上，建有非聚集索引，那么该非聚集索引将被用于查找数据行的位置，数据删除之后，位于索引叶子上的对应记录也将被删除。如果该表上有其它非聚集索引，则它们叶子结点上的相应数据也要删除。

 

如果删除的数据是该数所页中的唯一一条，则该页也被回收，同时需要更新各个索引树上的指针。

 

由于没有自动的合并功能，如果应用程序中有频繁的随机删除操作，最后可能导致表包含多个数据页，但每个页中只有少量数据。

 

 

• 聚集索引和非聚集索引的对比:

 

 

动作描述                  使用聚集索引         使用非聚集索引
列经常被分组排序            应                    应
返回某范围内的数据          应                   不应
一个或极少不同值            不应                  不应
小数目的不同值              应                    不应
大数目的不同值             不应                  应
频繁更新的列                    不应                  应
外键列                          应                    应
主键列                          应                    应

 

我们主要来看下：

                                      聚集        非聚集

小数目的不同值    (树低，大块连续)（树低，多个数据页）
大数目的不同值     (树高，同一数据页，重建索引成本高) （树高，不同数据页，可以直接命中）

 

个人觉得，对于大数目的不同值建什么类型的索引，没有绝对那个好，那个不好。要看运用的场合。

 

主键和另外一个字段都是大数目的不同值 ，其它索引的查询量大时，不建议把主键设置成聚集索引，个人意见。

 

虽然我们想尽办法去优化数据库，优化数据库索引，但当数据量很大时，性能会快速下降。

 

• 数据量大,树高，io高
• 不能支持全文搜索
  

这两个原因让我们去考虑用全文搜索引擎，比如lucene.