第6章DB的存储结构.ppt

* 6.6 小结（2） 索引顺序文件组织的主要缺陷是随着文件的增大，性能会下降。为了克服这个缺陷，可以使用B+树索引。B+树索引是平衡树，即从树根到树叶所有路径长度相等。这种查找是简单有效的，但插入和删除比较复杂。B树索引和B+树索引类似。B树的主要优点在于它去除了查找键值存储中的冗余；主要缺陷在于整体的复杂性以及结点大小给定时减少了扇出。实际应用中，人们几乎总是更愿意使用B+树索引。 基于散列的文件允许通过散列函数直接得到记录所在的桶地址。静态散列所用的桶地址集合是固定的，不容易适应DB数据量的快速增长。可扩充散列结构是一种允许修改散列函数的动态散列技术，在DB增加或缩减时它可以通过分裂或合并桶来适应DB大小的变化。 也可以用散列法创建辅助索引，这样的索引称为散列索引。 网格文件和分区散列等索引技术可以处理一般的有多个属性的索引。 * 6.4.1 散列机制（4） 图6.29 查找键为ENAME的散列组织 桶0 ZHOU C-343 750 桶5 桶1 桶6 ZHANG A-214 600 ZHANG B-467 600 桶2 LIU A-102 600 桶7 LIU B-215 800 LIU C-333 400 WEN B-306 700 桶3 HE F-257 800 桶8 LOU B-428 850 桶4 桶9 * 3．桶溢出的处理 在散列组织中，每个桶的空间是固定的，如果某个桶内已装满记录，还有新的记录要插入到该桶，那么称这种现象为“桶溢出”（也称为“散列碰撞”）。产生桶溢出的原因主要有以下两个： ●初始设计时桶数偏少。 ●由于散列函数的“均匀分布性”不好，造成某些桶存满了记录，而某些桶有较多空闲空间。 在设计散列函数时，桶数应放宽些，一般存储空间应有20%的余量，让它空闲着，以利减少桶溢出的机会。 但是不管散列函数如何好，再留有一定的存储空间余量，桶溢出现象难免还会发生。因而我们仍要有一系列处理溢出的方法，具体如下所述。 6.4.1 散列机制（5） * （1） 溢出桶拉链法（溢出链法）：如果某个桶b（称为基本桶）已装满记录，还有新的记录等待插入桶b，那么可以由系统提供一个溢出桶，用指针链接在桶b的后面。如果溢出桶也装满了，那么用类似的方法在其后面再链接一个溢出桶。这种方法称为溢出链方法。图6.30是这个方法的示意图。 6.4.1 散列机制（6） 桶0 桶1 桶2 桶3 桶1的 溢出桶链 图6.30 散列结构 的溢出链 * （2） 开放式散列法（open hashing） 这个方法是把桶的集合固定下来，也就是只考虑基本桶，不考虑溢出桶。如果有一个桶b装满了记录，那么就在桶集中挑选一个有空闲空间的桶，装入新记录。就桶的选择方法的不同，可分为下面两种： ●线性探查法：在桶b的下面（以循环的次序）顺序选择一个有空闲空间的桶，把新记录装进去。 ●再散列探查法：采用二次散列方法，跳跃式地选择一个有空闲空间的桶，装入新记录。 6.4.1 散列机制（7） * 上面开放式散列法一般使用在编译或汇编中构造符号表的情况。由于开放式散列法的删除操作比较复杂，因此数据库系统中使用封闭散列法。 散列方法的缺点是在系统实现时必须选择恰当的散列函数，并且不像索引结构那样随着数据量的变化容易变动。 标志散列组织装满程度的因子α称为“装填因子”或“负载因子”。α等于存储记录的空间量与给定的存储空间量的商。一般α取0.6 ~ 0.8。 如果α＞0.8，容易产生桶溢出； 如果α＜0.6，表示空间浪费太多。 6.4.1 散列机制（8） * 散列方法不仅可以用在文件组织上，也可以用在索引结构的创建上。“散列索引”是把查找键值与指针一起组合成散列文件结构的一种索引。 散列索引的构造方法如下：首先为主文件中每个查找键值建立一个索引记录；然后把这些索引记录组织成散列结构（称为“散列索引”），而不是稠密或稀疏索引结构。 例6.4 对图6.10的数据建立一个散列索引。 查找键为ENO（工号），对每个查找键值建立一个索引记录。散列函数可以这样构造：对工号中的数字部分，求出其和，然后除以7（即桶数为7），得到余数作为索引的桶地址。这样，散列索引有7个桶。假设每个桶可放2个索引记录，如果超过2个，就要链接溢出桶。对图6.10的数据建立的散列索引如图6.31所示。 6.4.2 散列索引（1） * 在这个例子中，ENO是一个候选键，每个ENO值只与一个主记录联系。一般，查找键值可以与多个主记录相联系，那么散列索引中的指针或者指向一个主记录，在主文件中再沿着指针链找到其它相应记录；或者指向一个桶，桶内存放指向主记录的指针。这些技术都是辅助索引中使用过的。 “散列索引”这个术语是指散列文件结构，也可以指辅助散列索引。 严格地讲，散列索