几种索引技术的比较谢力军1,杨军2(11怀化芷江师范学校,湖南怀化418008;21广东女子职业技术学院,广东广州511450)摘要:介绍了几种索引技术的概念及应用,讨论了稠密索引、稀疏索引、多级索引、辅助索引、B+树索引等机制1关键词:索引技术;主索引;辅助索引中图分类号:TP3111131文献标识码:A文章编号:1671-9743(2009)08-0115-04收稿日期:2009-07-24基金项目:湖南省科技计划项目(编号:2007FJ4232)1作者简介:谢力军(1964-),男,湖南会同人,芷江师范学校讲师,主要研究数据库技术、网格计算等11引言用户对数据库最频繁的操作是进行数据查询1一般情况下,数据库在进行查询操作时需要对整个表进行数据搜索1当表中的数据很多时,搜索数据就需要很长的时间,这就造成了服务器的资源浪费1为了提高检索数据的能力,数据库引入了索引机制1索引有主索引和辅助索引两种1主索引有稠密索引、稀疏索引和多级索引等形式1主索引的顺序决定了文件的排列顺序1其余索引称为辅助索引,辅助索引可以提高对非主索引的的查找键进行的查询效率,但是,他们通常会增加数据库修改的开销1索引顺序文件组织的主要缺陷是随着文件的增大,性能会下降1为了克服这个缺陷,可以使用B+树索引1B+树索引是平衡树,即从树根到树叶所有路径长度相等1这种查找是简单有效的,但插入和删除比较复杂1B树索引和B+树索引类似1B树的主要优点在于它去除了查找键值存储中的冗余;主要缺陷在于整体的复杂性以及结点大小给定时减少了扇出1实际应用中,人们总是更愿意使用B+树索引12几种索引技术的比较211索引顺序文件如果索引的查找键值的顺序与主文件的顺序一致,那么这种索引称为主索引,也称为聚类索引(clusteredindex)1如果文件按照某个搜索码的顺序物理存储,称这种在某个搜索码上有主索引的文件为索引顺序文件,如图211所示1图211索引顺序文件示意图第28卷第8期怀化学院学报Vol1281No182009年8月JOURNALOFHUAIHUAUNIVERSITYAug1,2009注意索引顺序中的/顺序0的两个误解:(1)不是指在存储介质上是顺序存放的,而是指按照某个值顺序排列的逻辑结构(例如,数据结构中的/表0),索引在存储介质上可能是按顺序存放的,也可能不是;(2)在搜索时并不是/从前往后,点一个名喊一声道0,而是要根据对于当前的搜索码该表是有序还是无序的分别采用顺序或随机的搜索方法1212稠密索引(DenseIndex)对主文件中每一个查找键值建立一个索引记录(索引项),索引记录包括查找键值和指向具有该值的记录链表中第一个记录的指针,这种索引称为稠密索引,如图212所示1图212稠密索引示意图213稀疏索引(SparseIndex)在主文件中,对若干个查找键值才建立一个索引记录,此时索引记录的内容仍和稠密索引一样,这种索引称为稀疏索引,如图213所示1图213稀疏索引示意图与稠密索引的每一个搜索码都有一个索引记录不同,稀疏索引只为部分搜索码建立了索引项1如果根据搜索码查找数据文件中的记录,而这个搜索码恰恰没有在稀疏索引的索引记录中,那么如何利用该稀疏索引进行查询呢?首先要在稀疏索引中找到小于特定值的最大搜索码的索引项所在的位置,然后根据索引项中的记录指针找到文件中的记录1由于是稀疏索引,找到的记录不一定是我们需要的,因此还要根据顺序文件的搜索码链表(记录在逻辑上按照搜索码顺序链接起来形成的)去查找我们需要的记录即可1另外,利用稠密索引通常可以比稀疏索引能够更快地定位一个记录的位置;再一点,与稠密索引相比,稀疏索引占用空间较小,插入和删除时维护的开销也小1那么在实践当中如何正确地建立稀疏索引呢?因为处理数据库查询的开销主要是由把数据块从磁盘上取到主存的时间来决定1一旦将数据块放入主存,扫描整个数据块的时间是可以忽略的1因此可以考虑为每个块建一个索引项的稀疏索引,使用这样的稀疏索引,可以定位包含所要查找记录的块1214多级索引(multi-levelindex)如对主索引再建立一级稀疏索引,即对每个索引块建立一个索引记录,就形成了二级索引1此时外层索引块可常驻内存,在查找记录时内层索引块只要读1次就行1#116#怀化学院学报2009年8月如果外层索引块的数目太多,不能全部进内存,那么可对最外层索引再外建一层索引,这就形成了多级索引技术,如图214所示1图214多级索引示意图215辅...
