Informix系列之谈谈索引

一、磁盘简介

磁盘由盘片构成，一个盘片上有扇区，通常为512字节（磁盘的最小存储单位）。若干扇区组成的同心圆，称为磁道

在盘片上面有用来读取数据的磁头，沿着机械臂在各个磁道间移动。在机器运行的时候盘片会以一定的转速绕主轴旋转（一般有5400rpm、7200rpm等）。

从硬盘上读取一次数据有以下步骤：

A：磁头移动的数据所在的柱面上（t1）。

B：盘片旋转将指定块旋转至磁头下（t2）。

C：磁头读取数据块的内容（t3）。

在一次数据读取过程中，主要的时间将花费在t1和t2上，特别t1最大有可能将达到0.1S。

二、B树介绍

二叉查找树其查找的时间复杂度与树的深度有关，在大规模数据存储中，树的高度必然过大，导致查找次数过多，即磁盘I/O过于频繁，效率低下。这样就提出了平衡多叉查找树，B-tree（Balance-TREE）就是这样一种数据结构。

一棵m阶的B树，有以下特性：

A：树中的每个节点最多含有m个孩子（m>=2）

B：除根节点和叶子节点外，其它每个节点至少有[ceil(m/2)]个孩子。

C：若根节点不是叶子节点，则根节点至少有两个子节点。

D：所有叶子节点都在同一层，叶子节点不包含任何关键字信息。

E：每个非终端节点中包含n个关键字信息，这些关键字按升序排序，指针p（i-1）所指向的子树中所有关键字均大于K（i-1）且小于Ki。关键子的数量需满足[ceil(m/2)-1]

A：根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。（磁盘IO操作 1次）

B：此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17

C：根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。(磁盘IO操作 2次)

D：此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26

E：根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。（磁盘IO操作 3次）

F：此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。

分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。文件越多B树相对于二叉查找树的优势就越大。

三、B+树

B+树是为满足文件系统需求而出现的一种B树的变型。它与B树的主要区别为：

A：所有的叶子节点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大的顺序链接，B树的叶子节点并没有包含全部需要查找的信息。

B：所有的非终端节点可以看成是索引部分，节点中仅含有其子树中最小（或最大）关键字，而B树的非终端节点也包含需要查找的有效信息。

为什么说B+树比B树更适合做数据库的索引呢？

A：因为B+树内部并没有指向具体关键字的指针，内部节点相对B树更小。所以相同的节点B+树能够存储更多的内容，可以进一步降低磁盘的io。

B：查询效率稳定，在B+树中任何关键字的查找，都需要走完一条从根到叶子节点的路。

C：B+树叶节点是有联系的，解决了遍历元素效率低的问题（数据库中经常基于范围查找）

附一个讲B树、B+树比较详细的帖子，里面有往树里添加元素的演示图

https://www.cnblogs.com/vincently/p/4526560.html

四、生成索引

发出create index语句时，对表采用独占锁，直到生成索引。发出命令的用户需要是数据库的DBA或指定表格的index权限。

Informix允许在指定dbspace中生产索引，称为分离索引，这样数据和索引可以在不同的硬盘上，可提高检索速度。若不指定dbspace，将在表格所在的dbspace中生成索引，若指定的dbspace空间不够，也在表格所在的dbspace内生成索引。

AIX上把磁盘分为外边缘、中央、内边缘等区域，根据磁盘的特性，可以将比较活跃的表格放在硬盘的中央区域，以提高性能。若对表格每次读写的数据较大，则可以把表格放在硬盘的外边缘（磁道的周长较长，一圈能够读写的数据相对多些，减少磁头移动）。

五、选择填充因子

Fillfactor表示informix索引节点的百分比。索引节点即B+树中的页，跟踪索引中的值。通过调整fillfactor可以调整以扩展或压缩索引，由于B+树是一棵平衡树，当某节点填满之后，为保持平衡性，将会有节点分裂等一些操作，需要磁盘io。

所以如果索引所在的表格今后还有大量的数据要新增，则可以选择较低的fillfactor，留下更多的索引增长空间，例如将fillfactor设置为50，则索引节点将占用50%空间，留下50%增长空间。如果表格日后不会有很多数据新增，则可以设置更高的值。

Create index cust1 on t_cust(last_name) fillfactor 50;

不同fillfactor值示意图

六、索引注意事项

其实索引注意事项还有很多，这里只是写几点平时网上可能不常见的吧。

a；避免在varchar字段上建索引，这种字段的长度可能发生变化，导致树里面的索引页发生变化。

b；在列值选择性较低的列上建索引（男，女 这样的列，一个值可能在树里面跨好几页），可以在末尾加一个列值选择性较高的列建立复合索引，提高索引的选择性。

c；在有些系统里面发生delete与insert可能会使每页的索引行减少，需要使用

oncheck –pT database:table

检查索引页填满程度。输出内容包含B+树的层数、每层的页数、每页的平均关键字数、每页的平均未使用字节数。

如果自由字节数占页长的比例大大增加，则应该删除并重建索引以提高性能。

d；应定期的执行update statistics更新系统表，避免查询优化器根据错误信息选择荒唐的路径。

e；还有informix的查询优化器以及set explain这部分内容。