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