《静态索引结构动态索引结构Trie树散列（Hashing）》由会员分享，可在线阅读，更多相关《静态索引结构动态索引结构Trie树散列（Hashing）（145页珍藏版）》请在金锄头文库上搜索。
1、n n静态索引结构静态索引结构n n动态索引结构动态索引结构n nTrieTrie树树n n散列散列 ( (Hashing)Hashing)静态索引结构静态索引结构n n示例：示例：有一个存放职工信息的数据表，每一个有一个存放职工信息的数据表，每一个 职工对象有近职工对象有近 1 1k k 字节的信息字节的信息, , 正好占据一个页正好占据一个页 块的存储空间块的存储空间。当数据对象个数当数据对象个数 n n 很大时，如果用无序表形式很大时，如果用无序表形式 的静态搜索结构存储，采用顺序搜索，则搜索效的静态搜索结构存储，采用顺序搜索，则搜索效 率极低。如果采用有序表存储形式的静态搜索结率极低。
2、如果采用有序表存储形式的静态搜索结 构，则插入新记录进行排序，时间开销也很可观构，则插入新记录进行排序，时间开销也很可观 。这时可采用索引方法来实现存储和搜索。这时可采用索引方法来实现存储和搜索。线性索引线性索引 ( (Linear Index List)Linear Index List)n n假设内存工作区仅能容纳假设内存工作区仅能容纳 64 64k k 字节的数据，在字节的数据，在 某一时刻内存最多可容纳某一时刻内存最多可容纳 64 64 个对象以供搜索。个对象以供搜索。n n如果对象总数有如果对象总数有 14400 14400 个个, , 不可能把所有对象不可能把所有对象 的数据一次都
3、读入内存。无论是顺序搜索或对的数据一次都读入内存。无论是顺序搜索或对 分搜索，都需要多次读取外存记录。分搜索，都需要多次读取外存记录。n n如果在索引表中每一个索引项占如果在索引表中每一个索引项占4 4个字节个字节, , 每个每个 索引项索引一个职工对象，则索引项索引一个职工对象，则 14400 14400 个索引项个索引项 需要需要 56.25 56.25k k 字节字节, , 在内存中可以容纳所有的索在内存中可以容纳所有的索 引项。引项。n n这样只需从外存中把索引表读入内存，经过搜这样只需从外存中把索引表读入内存，经过搜 索索引后确定了职工对象的存储地址，再经过索索引后确定了职工对象的存
4、储地址，再经过 1 1 次读取对象操作就可以完成搜索。次读取对象操作就可以完成搜索。n n稠密索引：稠密索引：一个索引项对应数据表中一个对象一个索引项对应数据表中一个对象 的索引结构。当对象在外存中按加入顺序存放的索引结构。当对象在外存中按加入顺序存放 而不是按关键码有序存放时必须采用稠密索引而不是按关键码有序存放时必须采用稠密索引 结构，这时的索引结构叫做索引非顺序结构。结构，这时的索引结构叫做索引非顺序结构。n n稀疏索引：稀疏索引：当对象在外存中有序存放时，可以当对象在外存中有序存放时，可以 把所有把所有 n n 个对象分为个对象分为 b b 个子表个子表( (块块) )存放，一个存放，
5、一个 索引项对应数据表中一组对象索引项对应数据表中一组对象( (子表子表) )。n n在子表中在子表中, , 所有对象可能按关键码有序地存放所有对象可能按关键码有序地存放, , 也可能无序地存放。但所有这些子表必须分块也可能无序地存放。但所有这些子表必须分块 有序，后一个子表中所有对象的关键码均大于有序，后一个子表中所有对象的关键码均大于 前一个子表中所有对象的关键码。它们都存放前一个子表中所有对象的关键码。它们都存放 在数据区中。另外建立一个索引表。在数据区中。另外建立一个索引表。n n索引表中每一表目叫做索引表中每一表目叫做索引项索引项，它记录了子表，它记录了子表 中最大关键码中最大关键码
6、max_keymax_key以及该子表在数据区中以及该子表在数据区中 的起始位置的起始位置objobj_ _addraddr。n n各个索引项在索引表中的序号与各个子表的块各个索引项在索引表中的序号与各个子表的块 号有一一对应的关系号有一一对应的关系：第：第 i i 个索引项是第个索引项是第 i i 个个 子表的索引项子表的索引项, , i i = 0, 1, , = 0, 1, , n n- -1 1。这样的索引结这样的索引结 构叫做索引顺序结构。构叫做索引顺序结构。n n对索引顺序结构进行搜索时，一般分为两级搜对索引顺序结构进行搜索时，一般分为两级搜 索。索。uu 先在先在索引表索引表 I
7、DID 中搜索给定值中搜索给定值 K K，确定满足确定满足IDID i i- -1.1.max_keymax_key class Mtree /基类 public:Triple protected:Mnode root;int m; AVLAVL树是树是2 2路搜索树。如果已知路搜索树。如果已知mm路搜索树的度路搜索树的度 mm 和它的高度和它的高度 h h, , 则树中的最大结点数为则树中的最大结点数为(等比级数前 h 项求和)n n每个结点中最多有每个结点中最多有 mm- -1 1 个关键码，在一棵高个关键码，在一棵高 度为度为 h h 的的 m m 路搜索树中关键码的最大个数为路搜索树中
8、关键码的最大个数为 mmh h+1+1- -1 1。uu 对于高度对于高度 h h=2 =2 的二叉树，关键码最大个数为的二叉树，关键码最大个数为7 7 ；uu 对于高度对于高度 h h=3 =3 的的3 3路搜索树，关键码最大个数路搜索树，关键码最大个数 为为 3 34 4- -1 = 801 = 80。struct Triple Mnode * r; /结点地址指针int i; char tag; /结点中关键码序号i ; /tag=0,搜索成功；tag=1,搜索不成功标识标识mm路搜索树结点的三元组表示路搜索树结点的三元组表示mm路搜索树上的搜索算法路搜索树上的搜索算法template
9、Triple /记录搜索结果三元组GetNode ( root ); /读入根结点Mnode *p = root, *q = NULL;while ( p != NULL ) /从根开始检测int i = 0; key(pn)+1 = MAXKEY; /监视哨while ( pkeyi+1 class Btree : public Mtree /继承 m 路搜索树的所有属性和操作public:int Insert ( const Typeint Remove ( const Type ;template class Mnode /结点定义 private:int n; /结点中关键码个数Mno
10、de *parent; /双亲指针Type keym+1; /关键码数组 1m-1Mnode *ptrm+1; /子树指针数组 0m ;B B_ _树的搜索算法树的搜索算法n nB_B_树的搜索算法继承了树的搜索算法继承了在在mm路搜索树路搜索树MtreeMtree上的上的 搜索算法。搜索算法。n nB_B_树的搜索过程是一个在结点内搜索和循某一树的搜索过程是一个在结点内搜索和循某一 条路径向下一层搜索交替进行的过程。因此，条路径向下一层搜索交替进行的过程。因此， B_B_树的搜索时间与树的搜索时间与B_B_树的阶数树的阶数mm和和B_B_树的高度树的高度 h h直接有关，必须加以权衡。直接有
11、关，必须加以权衡。n n在在B_B_树上进行搜索，搜索成功所需的时间取决树上进行搜索，搜索成功所需的时间取决 于关键码所在的层次，搜索不成功所需的时间于关键码所在的层次，搜索不成功所需的时间 取决于树的高度。如果我们定义取决于树的高度。如果我们定义B_B_树的高度树的高度h h 为失败结点所在的层次，需要了解树的高度为失败结点所在的层次，需要了解树的高度h h 与与 树中的关键码个数树中的关键码个数 N N 之间的关系。之间的关系。 n n设在设在 m m 阶阶B_B_树中，失败结点位于第树中，失败结点位于第 h h 层。在层。在 这棵这棵B_B_树中关键码个数树中关键码个数 N N 最小能达
12、到多少？最小能达到多少？ 从从B_B_树的定义知树的定义知, , uu 0 0层层 1 1 个结点个结点uu 1 1层层 至少至少 2 2 个结点个结点uu 2 2层层 至少至少 2 2 mm / 2 / 2 个结点个结点uu 3 3层层 至少至少 2 2 mm / 2 / 2 2 2 个结点个结点uu 如此类推，如此类推，uu h h- -1 1 层层 至少有至少有2 2 mm / 2 / 2 h h- -2 2个结点。所有这个结点。所有这 些结点都不是失败结点。些结点都不是失败结点。高度高度h h与关键码个数与关键码个数 N N 之间的关系之间的关系n n若树中关键码有若树中关键码有 N
13、N 个个, , 则失败结点数为则失败结点数为 N N +1+1。 这是因为失败一般发生在这是因为失败一般发生在 K Ki iint Btree:Insert ( const Type /找x的位置if ( !loc.tag ) return 0; /找到,不再插入Mnode *p = loc.r, *q; /未找到,插入Mnode *ap = NULL, *t;Type K = x; int j = loc.i;while (1) if ( pn ; /建立新结点move ( p, q, s, m ); /从 p向q 搬送 K = pkeys; ap = q; /分界关键码上移if ( ppa
14、rent != NULL ) /双亲结点不是根 t = pparent; GetNode (t); /读入双亲j = 0; key(tn)+1 = MAXKEY;while ( tkeyj+1 ; /创建新根rootn = 1; rootparent = NULL;rootkey1 = K; rootptr0 = p;rootptr1 = ap;qparent = pparent = root;PutNode (p); PutNode (q); PutNode (root);return 1; n n当分裂一个非根的结点时需要向磁盘写出当分裂一个非根的结点时需要向磁盘写出 2 2 个个 结点结点, , 当分裂根结点时需要写出当分裂根结点时需要写出 3 3 个结点。个结点。n n如果我们所用的内存工作区足够大，使得在向如果我们所用的内存工作区足够大，使得在向 下搜索时读入的结点在插入后向上分裂时不必下搜索时读入的结点在插入后向上分裂时不必 再从磁盘读入，那么，在完成一次插入操作时再从磁盘读入，那么，在完成一次插入操作时需要读写磁盘的次数需要读写磁盘的次数 = = = 找插入结点向下读盘次数找插入结点向下读盘次数 + + + 分裂非根结点时写盘次数分裂非根结点时写盘次数 + +
