索引与散列.ppt

静态索引结构
动态索引结构
散列(Hashing)
可扩充散列
小结
静态索引结构示例：有一个存放职工信息的数据表，每一个职工对象有近1k字节的信息,正好占据一个页块的存储空间。建立一个索引表便于数据的搜索。索引的优势：
有时数据文件很大不能一次全部装入内存，所以搜索一个数据对象无论是顺序搜索或对分搜索，都需要多次读取外存记录。
索引文件比数据文件要小的多，从外存中把索引表读入内存，经过搜索索引后确定了职工对象的存储地址，再经过1次读取对象操作就可以完成搜索。几个概念：
稠密索引：即一个索引项对应数据表中一个对象的索引结构。此时对象在外存中可不按关键码有序存放。此索引结构叫做索引非顺序结构。前面的例子就是一个稠密索引结构。
稀疏索引：当对象在外存中按关键码有序存放时，可以把所有n个对象分为b个子表(块)存放，一个索引项对应数据表中一组对象(子表)。下图是一个稀疏索引的例子。这样的索引结构叫做索引顺序结构。利用索引进行搜索
对索引顺序结构搜索时，一般分为两级搜索。
先在索引表中搜索给定值K，可以对分(折半)搜索，也可以顺序搜索。确定待查对象可能在的子表的序号i。
然后再在第i个子表中按给定值搜索要求的对象。各子表内各个对象如果也按对象关键码有序，可以采用对分搜索或顺序搜索；如果不是按对象关键码有序排列，只能顺序搜索。倒排表(InvertedIndexList)次索引结构
在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性值的对象按存放地址递增的顺序或按主关键码递增的顺序链接在一起。
次索引的索引项由次关键码、链表长度和链表本身等三部分组成。通过对“性别”和“婚否”次索引中的“女性”链和“已婚”链进行求“交”运算，就能够找到所有既是女性又已婚的职工对象倒排表
对于次索引结构当数据对象发生变化时需要对主索引和次索引都进行重排。这需要消耗很多时间。为此可采用倒排表。
倒排表（或倒排文件）是一种次索引的实现。在倒排表中所有次关键码的链都保存在次索引中，次索引记录对象存放位置的指针用主关键码表示，因此可以通过搜索次索引确定该对象的主关键码，再通过搜索主索引确定对象的存放地址。前面的图示就是一种简单的倒排表。
在倒排表中各个属性链表的长度大小不一，管理起来比较困难。为此引入单元式倒排表。单元式倒排表的索引项中存放的是对象所在硬件区域的标识，即一个能转换成地址的二进制数。整个次索引形成一个(二进制数的)位矩阵。单元式倒排表结构若要搜索“学建筑的广东籍男学生”，可以用一条AND把关于“男性”的位串、关于“广东”的位串和关于“建筑”的位串结合起来，就可得到搜索的位置。m路静态搜索树这种多级索引结构形成一种m叉树。树中每一个分支结点表示一个索引块，它最多存放m个索引项，每个索引项分别给出各子树结点(低一级索引块)的最大关键码和结点地址。这种m叉树用来作为多级索引，就是m路搜索树。
m路搜索树可以是静态索引结构，即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。
m路搜索树还可以是动态索引结构，即在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。动态搜索结构在子树Pi中所有的关键码都小于Ki+1，且大于Ki，0<i<n。
在子树Pn中所有的关键码都大于Kn；
在子树P0中的所有关键码都小于K1。
子树Pi也是m路搜索树，0in。
m路搜索树的类定义
template<classType>classMtree{//基类
public:
Triple<Type>&Search(constType&);
protected:
Mnode<Type>root;
intm;
}m路搜索树上的搜索算法
template<classType>
Triple<Type>&Mtree<Type>::Search(constType&x)
{
Tripleresult;//记录搜索结果三元组
GetNode(root);//读入根结点
Mnode<Type>*p=root,*q=NULL;
while(p!=NULL){//从根开始检测
inti=0;p→key[(p→n)+1]=MAXKEY;
while(p→key[i+1]<x)i++;//结点内搜索
if(p→key[i+1]==x){//搜索成功
result.r=p;result.i=i+1;result.tag=0;
returnresult;
}
q=p;p=p→ptr[i];//向下一层结点搜索
GetNode(p);//读入该结点
}
result.r=q;result.i=i;result.tag=1;
returnresult;//搜索失败,返回插入位置
}B树B树的类定义和B树结点类定义

template<