长江大学学报(自然科学版)2008年3月第5卷第1期:理工JournalofYangtzeUniversity(NatSciEdit)Mar12008,Vol15No11:Sci&Eng·233·B+树在数据库索引中的应用王英强(西安思源学院计算机科学与技术系,陕西西安710038)石永生(西安思源学院电子与信息工程系,陕西西安710038)[摘要]索引是数据库中建立记录间有规律排序的主要方式,它可以显著提高文件的操作速度。当数据库中记录的数目和数据量很大的时候,顺序查找速度会明显下降。为了提高查找速度,必须对文件建立索引。数据库索引的设计与实现有几种方法,主要阐述了使用B+树实现索引的方法。通过对B+树定义及算法的描述,可以看到使用B+树能够方便、有效的建立数据库的索引,并且能够有效减少查找时磁盘的I/O次数,提高数据查找的效率。[关键词]B+树;数据库;索引[中图分类号]TP311113[文献标识码]A[文章编号]167321409(2008)012N2332031索引在数据库中的作用在数据库系统的使用过程当中,数据的查询是使用最频繁的一种数据操作。当数据库中数据非常多的时候,数据查询的效率就是数据库系统用户最关心的问题。要提高数据查询的效率,最简单、有效的方法就是在数据表相应的列上建立索引。索引是对数据库表中一个或多个列的值进行排序的结构。与在表中搜索所有的行相比,索引用指针指向存储在表中指定列的数据值,然后根据指定的次序排列这些指针,有助于更快地获取信息。通常情况下,只有当经常查询索引列中的数据时,才需要在表上创建索引。索引将占用磁盘空间,并且影响数据更新的速度。但是在多数情况下,索引所带来的数据检索速度优势大大超过它的不足之处。2B+树的定义及特点B+树是一种用于数据库索引的数据结构,并且综合效率比较高。1)B+树的定义[1]一棵m阶的B+树或者为空树或者满足以下特性:①树中的每个节点最多有m个子树。②若根节点不是叶子节点,则至少有2个子树。③除根之外的非终端节点,至少有[m/2]个子树。④有K个子树的非叶节点恰好包含K个关键字。⑤所有的非叶子结点包含下列信息数据(P0,K1,P1,K2,,Pn-1,Kn),其中,Ki(i=1,2,,n)为关键字,且Ki<Ki+1;Pi(i=0,1,,n)为指向子树根结点的指针,且指针Pi-1所指子树中所有结点的关键字均小于Ki,Pn所指子树中所有结点的关键字均大于Kn。2)B+树的特点①有n棵子树的节点中含有n个关键字。②所有的叶子结点中包含了全部关键字的信息,及所指向含这些关键字记录的指针,且叶子节点本身依关键字的大小而自小到大的顺序链接。③所有非叶子结点可以看成是索引部分,结点中仅含有其子树中的最大(最小)关键字。3B+树的算法1)B+树的查询如果要查找关键字为K的所有记录,那么先在根节点中查找大于K的最小查找关键字Ki,然后沿着Ki左边的指针Pi-1到达第2层的节点;如果K大于根节点中的所有关键字,则沿着指针Pn到达第2层的节点。在第2层的节点中,用类似的方法找到一个指针,进入第3层的节点,直到B+树的叶子节点。在叶子节点中找到一个指针指向数据文件的记录。在B+树中进行查询的时候,若在非叶子结点上的关键字等于给定值,并不终止,而是继续向下直[收稿日期]2007212220[作者简介]王英强(19812),男,2003年大学毕业,助教,现主要从事数据库系统方面的研究工作。·234·长江大学学报(自然科学版)2008年3月到叶子结点。因此B+树的查找,不管成功与否,每次查找都是走了一条从根到叶子结点的途径。2)B+树的插入B+树的生成也是从空树起,逐个插入关键字而得。但由于B+树节点中的关键字个数必须大于等于[m/2],因此,每次插入一个关键字不是在树中添加一个叶子节点,而是先在最底层的某个非叶子节点中添加一个关键字,若该节点的关键字个数不超过m,则插入完成;否则要产生结点的“分裂”。分裂成的2个结点所含关键字的个数分别为[(m+1)/2](向下取整),[(m+1)/2](向上取整)。如果双亲结点有空间,则双亲结点应同时包含这2个结点中的最大关键字,如果没有空间,则分裂这个父亲结点为2个节点,再在上一层节点中加入新的关键字,一直向高层推进,乃至产生新的根节点,即B+树的高度增加了一层。3)B+树的删除若在B+树上删除一个关键字,则首先应该找到该关键字所在结点,并从中删除之,且有可能要合并节点。假若所删除关键字为非叶子节点中的Ki,则可以用指针P...