分布式数据库查询优化技术.doc

分布式数据库查询优化技术摘 要在分布式数据库中，由于高可靠性和高速度性是其重要特点，所以对查询执行的要求也就更高。而查询执行中查询优化是执行的关键环节，查询优化在很大程度上决定查询的效率或快慢。本文讨论的重点是对分布式查询执行的全局处理策略进行优化，尽可能避免通信代价的开销，并着眼于查询执行的实际代价，从分布式系统中选出一个最优的执行节点。从查询执行的效果出发，通过统计的方式，不断从最近的查询执行代价学习纠正最近查询执行的统计代价，为查询的全局处理提供参考，以达到优化执行、提高执行效率和速度的目的。1 分布式数据库概述1.1 分布式数据库的定义所谓分布式数据库系统就是由分布于多个计算机结点上的若干个数据库组成, 每个子数据库系统都是一个独立的数据库系统，它们都拥有各自的数据库、中央处理机、终端，以及各自的局部数据库管理系统，分布式数据库在使用上可视为一个完整的数据库,而实际上它是分布在地理分散的各个结点上。当然,分布在各个结点上的子数据库在逻辑上是相关的。简单的说，分布式数据库系统是一系列集中式数据库系统的联合。它们在逻辑上属于同一系统，但在物理结构上是分布式的1。1.2 分布式数据库系统的组成如图1-1所示，分布式数据库系统由以下述成分组成:(1)多台计算机设备，并由计算机网络连接。(2)计算机网络设备，网络通讯的一组软件。(3)分布式数据库管理系统，它包括GDBMS、LDBMS、CM,除了具有全局用户接口由GDBMS连接外，还可以具有自治场地用户接口，由场地DBMS链接，并持有独立的场地目录。(4)分布式数据库管理者（DDB），包括全局数据库(GDB)和局部数据库(LDB)以及自制场地的自治场地数据库。(5)分布式数据库管理者(DDBA)，它可分为二级，一级为全局数据库管理者(GDBA),另一级问局部或自治场地数据库管理者，统称为局部数据库管理者(LDBA)。(6)分布式数据库系统软件文档，这是一组与软件相匹配的软件文档及系统各种使用说明和文件。CommunicationNetworkS4S1S2S3图1-1 分布式数据库系统的结构1.3 分布式数据库系统的功能通常的集中式数据库管理系统应具备以下几个基本的功能2:(1)数据库定义功能;(2)数据存取功能;(3)数据库运行管理;(4)数据库的建立和维护功能。分布式数据库除了须具备以上集中式数据库的功能外，一般还须具有以下几个方面的功能:(1) 分布在网络中的各节点的数据库，其物理位置对用户透明;在用户眼里见到的只是整个系统中有哪些数据库，无论是本地还是远程数据库，用户操纵某一数据库就像操纵本地数据库一样。(2)处于网络中的各数据库共享的数据应保证一致性:当用户操纵(查询、更新、删除等)某一数据库时，整个网络中的各节点如果有该数据库的副本或备份数据库，应进行相应的更新操作，以保持数据一致性。(3) 系统的可靠性应比集中式数据库系统的可靠性更高: 如果因为某种原因，使系统中某一节点数据库崩溃，系统会自动选择另一具有该数据库的节点继续提供原来的服务。(4)支持多用户的并行访问，或者操作的并行性;(5)数据的安全性和完整性比集中式数据库要求更高; 由于分布式数据库系统中各节点数据库处于网络环境中，数据受到破坏和窃取以及丢失的可能性大大增加。2 数据库查询优化技术2.1 查询优化技术数据库系统研究的主要目标是尽可能的对用户隐藏数据结构的细节，使数据库系统的应用更能面向各个领域。同样，分布式数据库研究的主要目标之一是隐藏分布式环境的细节，使系统用起来更加简单、有效3。关系数据模型可以为集中式数据库提供一个数据无关的接口关系数据库语言是关系演算，使用该语言进行数据查询时，只需对要查询的数据进行简单的描述，而无须说明如何获取这些数据，SQL语言就是其中之一。但是，使用这种语言，也要对搜索、存取操作以及数据传输过程进行说明，因此，相应的查询优化技术的研究和发展也在不断进行。所谓查询优化，就是要保证查询总开销和总时间为最小。查询优化器的主要任务是控制和加快查询的执行和数据的传输过程。查找空间生成等价的QEP转化规则输入查询代价模型查找策略查询重写优化的逻辑查询计划(best QEP)查询优化器(如图2-1)首先以查询的某种表示作为输入，这种表示是查询处理器的语法分析子模块的输出，查询优化器为查询选择一种适当的数据存取策略。然而，查询优化一直是个复杂的问题，理想的全面的查询优化几乎是不可能的，许多专家和学者在这一领域曾做出过不少的研究和探讨，但总的说来，不尽人意，往往只能达到局部目标的查询优化效果，甚至有些理论并不适用。图2-1 查询优化处理 查询优化的基本类型通常包括两类:针对查询执行代价的优化和针对查询响应时间的优化。针对查询执行代价进行优化的目标是，使查询执行所使用的系统资源(总和)尽量地少，从而降低系统开销，整个系统的开销可以从单个系统资源的开销表达式中推出。针对查询响应时间优化的目标是尽量减少查询的响应时间，而不计较系统资源的耗费。2.2 分布式数据库优化设计分析在分布式数据库系统中，一方面，许多相对独立的处理器可能参与数据库操作。分布式数据库可能提供若干机会3：1)由于在处理一个问题时可以使用多台机器，并行以及加快查询反应速度的可能性增大。2)由于数据可以在多个节点上存在副本，系统可能不会仅仅由于一个节点或部件发生故障而不得不停止处理。另一方面，分布式处理增加了分布式系统各个方面的复杂性，因此即使是DBMS中最基本的组成本地优化本地模式优化本地查询查询组合全局模式在分布关系上的代数查询数据本地化分片模式在分布关系上的查询计算全局优化分片统计含有通信操作的优化的分片查询控制节点本地节点分片查询部分的设计，也得重新考虑。在许多分布式环境中，通信开销可能远大于处理开销，因此的问题是消息如何传送。比如分布式提交和分布式封锁。影响通信开销的因素主要是由于带宽开销迅速减小。某些类型的数据属于电子方式管理的大对象，因此即使在通信开销较小时，以太字节的数据传输开销也是不能忽视的。此外，通信开销常常不仅仅涉及数据传送，还有为数据传送做准备的各层协议、在接受方重建数据以及通信的管理。这些协议各自都需要大量的计算。尽管计算开销也在减小，与数据与关键数据库操作的传统单处理器操作相比，进行通信所需的计算可能仍不能忽视。分布式数据库查询处理如图2-5，分布特性的存在除带来通信开销外还影响到物理查询计划设计的复杂性和可选方案。在选择物理查询计划时必须考虑的问题包括：如果某个所需关系R有多个副本，那么应该从那个副本中获得R的值。当在两个关系R和S上实施某个操作例如连接时，有多个可选方案而且必须选择其中之一时，一些可能的选项如下：a)可以将S复制到R所在节点，并在该节点执行计算。b)可以将R复制到S所在节点，并在该节点执行计算。c)可以将R和S复制到二者各自所在节点之外的第三个节点，并在该节点执行计算。 哪种选择最好，这依赖于多个因素，其中包括哪个节点上有可用的处理时间以及操作结果是否需要与第三个结点上的数据相结合等。如果关系R有分布在若干节点上的片断,构成，那么在选择逻辑查询计划时，还应该考虑用 替代查询中使用的R，替代后的查询或许能很大程度的简化表达式。3)对局域网来说，通讯代价有着跟数据库的磁盘I/O代价相比拟的重要性。网络通信代价会随着用户数或负载的变化而改变，所以网络情况变化的随机性对分布式查询处理来说，更应该考虑通信代价。但当某个数据库的查询负载过高时，需要牺牲一定的通讯代价来提高执行的并行度。此外局域网络的广播能力可以用于全局优化更新、收集信息。图2-5分布式查询处理的通用层级方案3 分布式数据库查询优化技术研究3.1 基于分布式数据库分布特点的优化分布式并行系统处于网络中，处于网络中的各个节点具有单个服务器系统所没有的特性，所要考虑的因素和重点也将有所不同。分布式系统中数据的分布性和操作的并行性。所以既要利用分布并行特点来加快查询执行速度，又要尽量减少分布并行所带来的网络通信延迟代价3。3.1.1 系统环境和约束条件及设计目标(1)设计目标与系统环境本分布式数据库管理系统是针对局域网环境，分布式数据库是指分布于局域网络，而非广域网络，分布粒度为库一级，并且基于Mysql开源数据库来设计。目的是尽量避免数据库分布给查询执行带来的通信开销。(2)约束条件在此前提下，须考虑以下一些约束因素:1.通信代价分布式数据库不同于集中式数据库，所以通信代价不得不考虑；但同时它又没有广域网环境中的分布式数据库的通信开销那么大。所以既不能只考虑磁盘输入输出I/O和CPU计算代价的开销，也不能只考虑通信代价的开销，通过参考权威文献和对单机查询代价与数据通信代价的试验分析，二者都应考虑，且同时并重。由于是库级分布，不是表级分布，所以跨表操作始终只会在一个节点中进行处理。而跨库操作，目前Mysql数据库系统还不支持此种操作。因此，不存在查询时的服务器节点之间通信，因而省去对查询执行时通信代价的考虑。但是，当处理来自本节点没有的数据库时，就有可能了。在这种情况，传统的方式转发查询命令到其它节点上执行，这就要考虑通信代价的额外开销了2.查询分解表3-1 代价信息统计表节点IP数据库DB关系表table全局查询代价cost该表的负载数count.由于是库级分布，某个数据库在某个节点存在，那么这个数据库的所有表都在这个节点上存在(主本或副本)，所以不考虑查询分解。3.透明访问。用户访问本分布式数据库系统感觉不到数据库物理位置位于何处，就像访问本地数据库(或集中式数据库)一样。4.Mysql不支持的特性Mysql不支持视图、子查询、存储过程和触发器、外键。(3)优化目标强调查询快捷，着眼于查询时间的开销;注重整体查询(整个分布式局域网系统和多路多线程的总体查询)效率和吞吐率，而非单机或具体某一条查询语句的执行效率。系统合理假设主要针对上层进行优化，而不针对下层，并假定已对查询语句进行了优化。因此，要考虑的关键问题便落在通信代价上，而其它磁盘输入输出I/O和CPU计算代价的开销，是由下层查询优化去处理。3.1.2 优化策略研究与设计下面对启发式查询路径选择的优化策略进行详细探讨和设计。(1)基本思想根据最近一段时间的查询代价，推断局域网络中分布式数据库各节点当前的查询处理能力，实质上还是根据资源占用状况来选择一台较优的节点去执行查询处理。在实现策略上，属于不断学习优化的过程。基于一条基本思想:最近访问的表格，在最近一段时间内，仍处于同一状态(忙)，即很可能被再次访问。假如这种判断出现错误，也会仅仅因为一次的查询操作，而只误导一次，在下一次同样的查询，又会转入正确的优化判断。这样的“误判”，仅仅造成一次慢速的查询，不会有太大的损失。优化的另一策略是尽量避免通信代价的开销，使一个查询尽量不经过查询中转，避免查询结果数据的通信。(2)优化设计1.节点代价信息表为了记录上次访问表的查询代价，及其通信代价，需要设计以下一些表格如表3-1，以记录如下一些上次访问的历史信息：说明：(此处的通信代价不是指一次查询的所有数据的通信代价，是单位数据在当时的通信代价)节点IP：指示局域网中分布式数据库所在的节点的IP地址数据库：指该节点中存在有哪些数据库关系表：指该数据库中存在有哪些表用户数：指该表中当时有几个用户查询的计数为使各节点便于查询，该表存在于局域网中每一个节点中，而且为了提高查询速度，更快的执行优化选择，该表必须常驻内存。表中记录信息随时更新。全局查询代价由Mysql数据库系统本身的THD结构获得。某个表的用户计数是通过查询时锁表机制而获得。值得说明的是为什么不能采用共享数据结构方式?如果分布式网络中各节点共享一张表，表面上看起来，可以节省存储分配，维护单一;实际上，由于该表访问比较频繁，特别是查询用户量增大的时候更是如此，而为了保证数据的一致性，各节点必须互斥访问该表，无论采用锁机制，还是简单的互斥信号量，都会造成访问因竞争而等待，致使服务器处理性能大为降低。因此，它是不符合分布式系统设计思想的。2.代价的估算1)操纵单表的查询语句一个分布式数据库查询的执行，包括全局处理和本地处理两个阶段，相应的查询代价也包括全局处理代价和局部处理代价两部分，撇开CPU的开销，可以一个公式近似简化为：全局查询代价二通信代价+本地执行代价但基于前面的考虑，不计通信代价，所以只有本地执行代价。本地执行代价=CPU计算时间+I/O等待时间由于CPU计算时间相对很小，可以忽略，执行代价近似等于I/O等待时间。实现中，统计的代价为：I/O数据量可以粗略的以一个表的所有元组数计。2)操纵多表的查询语句需要注意的是，如果一条查询语句需要操纵不只一个数据库的一个表时，到底以哪个表的代价为准，或者都考虑但多个表之间考虑的偏重程度可能不一样，并不平均对待。所以衡量多个表操纵的查询代价，不能简单的将多个表代价相加之和作为该查询语句的代价。统计操纵多表的查询语句的代价时，很难将总体代价定位在各个表上，一些繁琐的算法既费时，又不准确，所以，基于实际应用上的考虑，略去本次查询的代价统计，而只统计单表操作的代价。多表属于同一数据库(对库级分布，一定位于同一结点上)，理论上，任选其中一个表的代价来衡量，但在实际操作中，为了减少单个表带来的偶然误判，采用累加和。多表不属于同一数据库(不一定位于同一结点上)，此种情况，当然不能像上面一样，任选一个表的代价去衡量，也不能将各表的代价累加之和作为痕量的代价。只能根据哪个表的操作代价高来决定执行节点。但对库级分布的数据库不支持多表不属于一个数据库的情况。3.负载这里讨论的负载主要指用户数量，以表作资源对象，用在某个表上的等待的线程(用户数)来度量负载。计数策略:由于多个查询可能操纵同一表，为保证数据的一致性，本分布式数据库系统提供了互斥锁(读锁和写锁)机制。当一个操纵某个表的查询请求到来时，就将count计数作加1操作，当该表的一个操作结束;当解锁一次，就将count计数作减I操作。然后定期更新此。ount计数。为此，需要在THD的结构里定义一个变量以保存该计数值。4.统计策略对代价的统计，取一定时间内，每次查询的代价的平均值。这里的一定时间即为统计周期，也是更新周期。同样，将每次查询的代价记入THD结构里，也将代价的平均值保存到THD结构里。以便全局优化器能方便获取所需信息。采用动态更新，即服务器一启动便开始统计，在服务器运行过程中周期性更新。所以全局代价表从无到有，逐渐增多，随着时间的推移，使查询优化信息越来越完善，越来越准确。另外，如果本次查询的表在全局代价表里尚未存在记录，则该次查询代价立即记入全局代价表中，以被后来的查询参考。不必等到一定周期的统计。某一次的统计可能不是准确的，但多次大量的统计，正确率总是符合正态分布的，从统计学的角度讲，是正确的、实用的。另外，为了使统计更为真实和有效，本设计对一些很少出现的一些语句抛弃掉，不予统计。比如像CREATE DATABASE, DROP DATABASE, CREATE TABLEDROP TABLE, ALTER TABLE, CREATE INDEX, DROP INDEX，等只有再创建数据库时，才会用到的一些命令语句;还有一些显示数据库及其分布信息的查询命令，以及全局视图查询命令，由于较少使用或不涉及具体操纵哪个表，也不予统计其代价信息，如SHOW DATABASE, SHOW TABLES, SHOW GLOBALDBS，SHOW IPSBYDB等。5.更新周期周期如何确定呢?周期过短可能造成统计的平均值不真实;但周期过长，有可能不能反应当时或最近的服务器节点的处理情况。所以周期既不能过长也不能过短，如何确定一个合适的周期呢?首先，这个周期不能是固定不变的，因为网络情况不是固定不变的，它会随着服务器节点负载而变化，而服务器节点的负载情况完全是随机的，随着用户数量的变化而变化。因此，为了适应变化多端的网络环境及节点资源负载情况，这里使用一种动态策略，以更准确更及时地反应服务器的处理能力。从实际情况出发，如果前后几次波动很大，超过一定的值，说明负载变化很频繁，这时，需要缩短统计周期;反之，可以加长统计周期。但为了防止变化过于平凡，造成“抖动”现象，一次不能偏离初始值过大。怎样确定偏离多大呢?可以以本次估计的代价，与上次代价估计的偏离程度来作调整。当这里的P根据服务器运行情况，可以由系统管理员确定。同样，当说明，如果本次统计代价与上次统计相比波动较大，偏离程度超过P%，周期变长；反之，周期缩短。初始值可以由系统管理员更改，默认为每30秒更新一次。6.更新策略为了保证优化信息的全局一致性，必须将各节点本地的最新统计的优化信息告知分布式系统中其它节点，使得对任何一个节点来，从理论上说，在当前的优化条件下，均会作出同样的选择(某个优化节点)。由于本文讨论的分布式数据库系统是存在于局域网络中，其可靠性和速度比较高，所以本文采用类似于选路信息协议(RIP)中路由信息在路由器间更新的策略，即广播策略。它避免了设定一张全局唯一的代价信息表，它属于共享资源，必须互斥访问，需要使用互斥锁机制才能实现。广播周期:为了防止广播风暴，不能频繁的广播消息，但是广播周期过于长，又会使全局优化信息得不到及时更新。设定一个阀值，当改变超过某一阀值时，才广播更新消息。7.问题简化1)关于数据库表的索引如果为数据库的表创建了索引，则在查询执行时的磁盘输入输出操作会与没有创建索引的表的代价低很多，因为查询时的扫描表分为两种:一种是表一扫描;另一种为索引一扫描。由于索引扫描时，能很快定位所需记录(元组数)所在磁盘块的位置，所以比将整张表的记录都读入内存来查询比较效率要高得多。但创建了索引的表的列较少，大多数表的大多数列没有创建索引。而且对同一个表，每一次查询统计均是以相同的方式统计，所以并不造成影响。对一些很少使用或者查询不涉及具体哪个表的简单操作，不予统计其代价信息，以尽量减少或避免统计数据的不真实性。2) CPU计算代价由于在查询执行中，CPU计算时间，比起磁盘输入输出和通信代价来说很小，在通常的优化器设计中，大都忽略不计，本优化也不予考虑。8.非更新数据库操作的并行化处理若某一刻，同时有多个用户查询请求访问同一表，并且是除插入、删除等更新操作以外的操作(非更新操作)，将查询命令分发出去并行处理。尽管单从代价来考虑，可能某一个服务器节点当前是最优选择的节点，但如果同一时刻(或某一段较小时间内)有多个客户请求到达，都要查询某个数据库的某个表，即竞争到同一张表上，必然形成等待队列。如果这些查询不都是更新性表操作，即非更新性操作是可并行化处理的，可以将非更新性操作分发到其它客户数较少的节点上去处理。如果同一查询语句操纵多个表，遇到此种情况，优化选择时就排除该表不计算其代价。9.全局优化信息表的存储组织本表常驻内存，所以其存储组织不能有较大的浪费。如果采用链表方式存储，表大小可以随时增加或减少，内存可以随时申请和释放，得到充分利用，但是，查找速度较慢。另一方面，由于提高查询速度和查询效率是本优化设计的目的，所以如何组织存储结构才能提高查找性能(速度)，是首要考虑的问题，所以使用数组存储方式就不太合适。而顺序存储方式比链表检索速度快，而且恰当的利用索引可以更高的提高查找速度。但由于不能事先预知该表信息的大小，而且可能动态改变，怎样解决数组固定大小的问题呢?由于此种变化并不频繁，可以使用new操作重新分配改变大小后的内存空间，并将原数据拷贝过去。而且对于本表来说，采用索引顺序存储方式，比起完全不采用索引的顺序存储方式或链表存储方式来说，避免了较大的不必要的数据重复存储，如表的前两项“数据库名”和“表名”无须重复存储。存储结构采用索引顺序表组织，分两级索引，如图3-1所示：表名标志（状态）地址（位置）长度表大小统计代价统计次数图3-1代价信息的索引顺序表存储结构第一级索引为数据库名，按数据库名的字母顺序有序排列；再按照数据库分成多个二级索引，即表索引，按表名的字母顺序有序排列。然后根据表来查找查询所要操纵的表相应的代价及客户计数及所在节点的IP等优化信息。由于整个系统中不同的数据库、表和节点IP的数量并不太大，所以按照两级索引来查找顺序代价表，很快便能找到优化的表处理节点(IP )。图中右半部分为顺序表，按表的第一项(代价cost)有序排列。关于索引顺序表的大小的确定：由于本表常驻内存，所以存储空间的分配不能又较大的浪费。所以为了充分利用存储空间，有两种分配方案:一种分配方案是，采用静态数组，但需要预先确定数组大小。在分配顺序表时，要预先确定表及索引的大小。如果是系统中第一个节点初始启动，可以在系统初启时，从Des Mysql底层预先获得数据库、各数据库的表及节点的数目，然后再分配存储空间并初始化各项数据，其中，表中的所有代价初始化为0(系统初启时，没有任何负载，所以这也是合理的)。如果不是系统中的第一个节点初始启动，只将本节点的所有数据库的所有表设为0，而将其它节点的数据库的表的代价暂定为无穷大;在未来的一段时间内，可以通过别的节点对全局优化信息表的广播信息获取来得到更新。另一种分配方案是，采用顺序表的动态存储分配，在系统启动后，通过分布式系统中其它节点的广播信息，根据需要，临时申请存储分配。这样，表的大小可以不一次性分配完，可以由小到大，随着表信息的不断增加而增大。10.索引顺序表的操作与互斥锁1)操作a)索引查找才能实现对上述索引顺序表的操纵，设计怎样的数据结构才能达到索引的目的?要索引某一项，需要知道被索引的表的地址，即索引表存放在哪个内存地址段中，可以用一个全局变量来记录;然后才能定位某级索引的相对位置(即地址偏移)，以及该级索引所覆盖的范围，即长度。对第一级索引(数据库索引)：数据库名标志（状态）地址（位置）长度对第二级索引(表索引):对顺序代价表：代价信息标志（状态）说明:对第一、二级索引中增加的“标志位”，指的是表(库)的当前状态：1表示该表(库)存在且可用；0表示该表(库)当前不可用；其中二级索引中新增加的“统计代价”，是指在更新周期内的统计代价，它只作临时记录用，不作优化信息用，等到周期一到，才决定是否将其代价值加到代价Cost列上。二级索引中新增加的“表大小”，是指表的每条记录的大小与记录数数的乘积；新增加“统计次数”记录该表的被统计的次数。同样，对顺序表的“标志位”，1表示该代价信息可用;0表示该代价信息不可用。顺序代价表的“代价信息”，指的是上图中所列的代价Cost、客户计数Count和节点IP等信息。注释：为什么要将“统计代价”和“统计次数”两项加到二级索引表中，而不加到顺序代价表中，有两个方面的原因：一是因为这两项查询使用频繁，每次查询都要查找某个数据库的某个表的这两项，用以统计查询代价：第二级索引表的表项数量比顺序代价表小，加之搜索级数低于到顺序代价表的搜索，所以加快了搜索速度。二是因为，将此两项放在顺序代价表里，浪费存储空间，因为只有本节点的数据库中的表才会被统计到(能够查询到本节点的自然是本结点上有的数据库及其表)，如果将此两项放在代价信息表里，那么必然造成大量的代价表项(其它节点IP)也分配了相同的此两项空白存储空间；而通过前两级索引，已经能够唯一区分本节点各个数据库的各个表的代价信息的记录。b)更改删除:如果某个表被删除，首先在标志位置0，然后，将后面的表项依次往前移动;同时，须将顺序代价表中的相应代价节点项全部置为0，但无需将后面的表项往前移动。尽管这种操作，可能较慢，但这样的操作毕竟极少发生，比起大量的查询查询操作来说，可以忽略它。而且对绝大多数查询用户没有删除表的权限。插入：如果某个表的优化信息是索引顺序表中没有过的，这时，需要在索引表中增加一个表项，记录其优化信息。首先在该数据库的第二级索引表的尾部查找是否有标志位置为0的表项，如果有，将该表项填入，并调整顺序使其有序。如果没有，再在该数据库的第二级索引表段中查找是否有标志位置为0的表项，如果有，将该表项填入，调整顺序使其有序。如果仍然没有，就须重新申请分配更大存储空间，然后将原有的记录项移置过去，并将新的表项按序插入，使其保持有序。此种情况出现的机率虽然极少，但仍可以尽量避免，那就是采用预留策略。即对各个数据库的表段预留一定的空表项，以备插入新的表项用。预留表项的数目保持一个阀值，如果因为出现删除表项，而使得预留的空表项数目大于这个阀值一定数目，就将多余阀值的空表项删除，这时，就须要对索引表作移置操作；反之，如