第三章 索引与散列

第三章索引和散列3．1基本概念3．2顺序索引3．3B＋树索引文件3．4B树索引文件3．5静态散列3．6动态散列3．7顺序索引和散列的比较3．8(略)SQL中的索引定义3．9多码访问3．1基本概念•顺序索引(orderedindex)：基于对值的一种排序•散列索引(hashindex)：用散列函数将值分布到若干个散列桶中。影响索引效率的因素：•访问类型•访问时间•插入时间•删除时间•空间开销搜索码（searchkey)3．2顺序索引*主索引(PrimaryIndex)：包含记录的文件按照某个搜索码指定顺序排列，那么该搜索码对应的索引称为主索引。主索引也称为聚集索引(ClusteringIndex)。通常情况下，主索引建在主码之上。*辅助索引：顺序与文件中记录的物理顺序不同的索引称为辅助索引(SecondaryIndex)或非聚集索引(NonclusteringIndex)3.2.1主索引：文件按某个搜索码顺序存储。称这种在某个搜索码上有主索引的文件为索引顺序文件（index-sequentialfile)。适合对整个文件进行顺序处理又需要对文件的单独记录进行随机访问的应用1.稠密索引和稀疏索引2.多级索引3.索引的更新插入：稠密索引稀疏索引删除：稠密索引稀疏索引3.2.2辅助索引：辅助索引必须是稠密索引,对每个搜索码值都有一个索引项。3．3B＋树索引文件B＋树是一个平衡的多叉树。1.B＋树的结构2.B＋树上的查询3.B＋树的更新4.B＋树文件组织3．3.1B＋树的结构B＋树索引是一个多级索引(1)B＋树结点结构P1K1P2…Pn-1Kn-1Pn有n-1个搜索码K1、K2、…、Kn-1，n个指针P1、…、Pn。结点中码值有序存放：如果ij,则KiKj。(2)叶结点结构，对于i=1,2,…，n-1。指针Pi指向具有Ki的一个文件记录（主索引文件按照码值存放）或指向一个指针桶（辅助索引），桶中每个指针指向具有码值Ki的一个文件记录。指针Pn指向下一个叶结点的头指针。这样可以将叶结点按照码值顺序串在一起，以便对文件进行顺序处理。叶结点中最多有n-1个码值，至少有(n-1)/2个码值，各叶结点中值地范围互不相交，即若Li和Lj是两个叶结点且ij，那么Li中的所有码值都小于Lj中的所有码值。要使B＋树索引成为稠密索引，各码值必须出现在叶结点中。(3)B＋树的非叶结点，形成叶结点上的一个多级（稀疏）索引。对于i=2,3,…，n-1，指针Pi指向一棵子树，该子树中所有结点的索引码值大于等于Ki－1且小于Ki，Pn指向的子树中所有码值大于等于Kn-1，P1指向子树中的所有码值均小于K1。非叶结点中至少有n/2个指针，最多有n个，指针个数称为该结点的扇出。(4)根结点：根结点的指针数可以小于n/2。除非整棵树只有一个结点，否则，根结点至少有两个指针。完整的B＋树。如图：有两种方法:一、从最小码值起顺序查找;二、从根结点开始，进行随机查找。随机查找:从根开始(查找长度小于logn/2k)。2B＋树上的查询3．3.3B＋树的更新插入时结点过大，要进行分裂，删除时，结点过小要合并，只要这样才能保B＋树的平衡特性。*插入：(1)结点不会过大，直接插入(2)分裂结点，有n个码分裂插入例子：在前面的插入B+树中加入branch-name值为“Clearview”的一条记录。按照查找算法，“Clearview”应出现在包含“Brighton”和“Downtown”的结点中。该结点已经没有插入“Clearview”的空间，因此该结点分裂为两个结点。图12-12在分裂结点后，必须将这个新结点加入B+树中，新结点的最小搜索码值“Downtown”，需要将该搜索码值插入到被分裂的结点的父结点中。由于父结点中有插入搜索码值的空间，直接插入即可。图12-12，如果父结点也没有空间，那么父结点分裂。最坏的情况下，一直分裂到根，树的深度增加。算法：procedureinsert(valueK,pointP)找到应该包含值K的叶结点Lif(L所含的搜索码少于n-1个)theninsert_in_leaf(L,K,P)elsebegin/*L已经含有n-1搜索码，分裂L*/创建结点L’把L.P1,…,L.Kn-1复制到可以存储n个（指针，搜索码）对的内存块Tinsert_in_leaf(T,K,P)令L’.Pn=L.Pn;令L.Pn=L’从L中删除L.P1,…,L.Kn-1把T.P1,…,T.Kn/2|从T中复制到L中，以L.P1作为开始把T.Kn/2|+1,…,T.Kn从T中复制到L’中，以L’.P1作为开始令K’表示L’中最小搜索码值insert_in_parent(L,K’,L’)end插入叶结点procedureinsert_in_leaf(nodeL,valueK,pointP)if(KL.K1)then把P，K插入L中，紧接在L.P1前面elsebegin令Ki表示L中小于K的最大搜索码值把P，K插入L中，紧接在T.Ki后面end插入双亲procedureinsert_in_parent(nodeN,valueK’，nodeN’)ifN是树的根结点thenbegin创建新结点R包含N,K’，N’/*N和N’都是指针*/令为树的根结点returnend令P=parent(N)if（P包含的指针小于n个）then将(K’,N’)插入到P中N后面elsebegin/*分裂P*/将P复制到可以存放P以及(K’,N’)的内存块T中把结点(K’,N’)插入T中紧跟在N后面删除P中所有项；创建结点P’把T.P1,…,T.Pn/2|复制到P令K’’=T.Kn/2|把T.Kn/2|+1,…,T.Pn+1复制到P’insert_in_parent(P,K’’p’)end*删除：•从图12-12的B+树中删除“Downtown”。用查找算法，定位“Downtown”的索引项。当从“Downtown”索引项所在的叶结点中把它删除后，叶结点变为空。这个结点必须从树中删除。删除叶结点后，必须从父结点中删除指向它的指针。父结点有三个指针，删除后，还有两个指针，结点足够大。删除操作结束。图12-14•当要对叶结点的父结点删除时，父结点本身可能会变的很小。如：我们要从图12-14的B+树中删除“Perryridge”时发生。对“Perryridge”的删除使一个叶结点变空。当删除父结点中的指针时，父结点中只剩下一个指针，合并结点。看它的兄弟结点（包含一个搜索码Mianus的非叶结点）的情况。兄弟结点有空间，因此合并两结点。图12-14。可以看到删除操作后根结点只有一个指针，根结点也要被删除，整个B+树减少一层。•合并结点有时候也并不可行。如果从图12-12的B+树中删除“Perryridge”，包含“Perryridge”的结点删除为空，这个叶结点的父结点仅剩一个指针，但是，这次却不能与它的兄弟结点合并。解决的方法是重新分布指针，使每个结点包含两个指针。图12-16。注意值的重新分布使两兄弟的父结点中的搜索码值发生改变。算法：proceduredelete(valueK,pointerP)找得包含(V,P)的叶结点Ldelete_entry(L,K,P)proceduredelete_entry(nodeN,valueK,pointerP)从N中删除(K,P)if(N是根且N只剩下一个子结点)then使N的子结点成为新的树根结点并删除Nelseif(N值指针太少)thenbegin令N’为parent(N)的前一子女或后一子女令K’为parent(N)中指针N和N’之间的值if(N和N’中的项能放在一个结点中)thenbegin/*合并结点*/if(N是N’的前驱)thenswap_variables(N,N’)if(N是非叶结点)then将K’以及N中所有指针和值附加到N’中else将N中所有(Ki,Pi)对附加到N’中；置N’.Pn=N.Pndelete_entry(parent(N),K’,N);删除结点Nendelsebegin/*重新分布：从N’借一个索引项*/if(N是N’的前驱)thenbeginif(N是非叶结点)thenbegin令m满足N’.Pm是N’的最后一个指针从N’中去除(N’.Lm-1,N’.Pm)插入(N’,Pm,K’)并通过将其他指针和值右移使之成为N’中的第一个指针和值用N’.Km-1替换parent(N)中的K’endelsebegin令m满足(N’.Pm,N’.Km)是N’中的最后一指针/值对从N’中去除(N’.Pm,N’.Km)插入(N’.Pm,N’.Km)并通过将其他指针和值右移使之成为N’中的第一个指针和值用N’.Km替换parent(N)中的K’endendelse…与then的情况对称…endend4B＋树文件组织B＋树文件组织中，树叶结点中存贮的是记录而不是指向记录的指针。插入、删除同B＋树索引一样。如图：3．4B树索引文件B树索引和B＋树索引相似。区别：B树去除了搜索码值存贮中的冗余。B树允许搜索码值只出现一次。如图：3．5静态散列1．散列文件组织在散列文件组织中，通过计算所需记录搜索码上的一个函数，直接获得包含该记录的磁盘块地址。桶――能存贮一条或多条记录的一个存储单位。通常一个桶为一个磁盘块，但也可能大于或小于一个磁盘块。K――码值集合。B――桶地址集合。H――从K到B的一个函数，称为散列函数。插入ki时，计算h(ki)得到存放该记录的桶地址。查找ki时，同样计算h(ki)。删除：计算h(ki),找到ki删除。有时会出现：kikj,h(ki)=h(kj)的情况，称为冲突。(1)散列函数要求：(a)分布均匀,每个桶分配到的记录数相同。(b)分布是随机的。实际中不可能做到。(2)桶溢出控制溢出原因：•桶不足，桶数比实际需要多20％。•偏斜，某些桶分到的记录比其它桶多。1)多个记录码值相同。2)h不好造成分布不均匀。溢出桶用溢出链表示――闭散列，数据库常用。2．散列索引3．6动态散列静态散列技术要求固定桶地址集合B，这存在一个问题，大多数数据库都会随时间而变大，要用静态索引，可以：(1)根据当前文件大小选择散列函数，性能随数据库增大而下降。(2)根据将来某个时刻文件的大小选择散列函数，初始时会造成空间浪费。(3)随文件增大，周期性对散列结构重组。重组时，新的散列函数选择、记录重新散列。重组是一项复杂、耗时的工作，重组时要禁止对文件的访问。动态散列：允许散列函数动态改变，以适应数据库增大或缩小的需要。1.Trie树当码是可变长时，Trie树是一种特别有用的索引结构。Trie树是一棵度大于等于2的树。它的每一层分支不是由整个码值决定的，而是由码值的一部分决定的。•Trie树的查找•Trie树的插入•Trie树的删除2.Trie树做索引参考“数据结构”清华大学殷人昆等(1)可扩充散列，Fagin等[1979]可扩充散列：(a)思想：当数据库增大或缩小时，可扩充散列可以通过桶的分裂和合并来适应数据库大小的变化。(b)好处：空间效率得以保持，每次重组仅作用于一个桶上，时间开销也比较低。(c)h，应具有均匀性和随机性，这里h为每个码计算出一个k位二进制序列。(d)查找：为了确定含有搜索码值kl的桶位置，先找到h(kl)高i位二进制字串对应的表项，再根据表项中的指针得到桶的位置。(e)插入：要插入kl，用相同的方法定位桶，假定为j桶：(i)如果j桶中有剩余位置，将新记录插入即可；(ii)如果桶j已满，分裂桶j，并将该桶中现有记录和新记录一起重新分配。分裂桶之前，还必须根据散列值确定是否需要增加所需要的位数。如图：i=ij:桶地址中只有一个表项指向桶j，需增加桶地址表的大小，以容纳桶j分裂而产生的两个桶指针。为此，散列值增加1位，i+1，桶地址表的大小加倍。iij:那么桶地址表中有多个表项指向桶j。因此可以直接分裂桶，指向桶j的表项的散列前缀的最左ij位相同。(f)删除：删kl，查到kl，如为桶j，从桶j中删