第2章一维索引组织结构

1、2022年6月13日1高级数据库课程高级数据库课程第第2章：一维索引组织结构章：一维索引组织结构 引言引言 整个关系在储存中如何存储与表示？以整个关系在储存中如何存储与表示？以及怎样才能有效检索与定位？及怎样才能有效检索与定位？ 比如，如何回答象比如，如何回答象 SELECT * FROM R 这样一个简单查询？这样一个简单查询？ 2022年6月13日2引言引言我们可能不得不检索辅存中的我们可能不得不检索辅存中的与数据库与数据库文件对应的文件对应的每个存储块，且还得依赖块每个存储块，且还得依赖块首部中存在足够得信息来表明该块记录首部中存在足够得信息来表明该块记录从什么地方开始，块中记录属于什么

2、关从什么地方开始，块中记录属于什么关系；系；有效的解决方案有效的解决方案采用索引结构采用索引结构；2022年6月13日3索引：索引：索引是一种数据结构，它以记录的特征（通常是一个或多个字段的值）为输入，并能“快速地”找出具有该特征的记录2022年6月13日4引言引言 查找键-建立索引的字段 索引方法（1）顺序文件上的简单索引（2）非排序文件上的辅助索引（3）B树, 一种可以在任何文件上建立索引的常用方法（4）散列表2022年6月13日52.1顺序文件上的索引顺序文件上的索引相关概念相关概念 数据文件数据文件 存放一个关系所有元组数据的文件；存放一个关系所有元组数据的文件； 顺序文件顺序文件 按

3、关系中指定的一个或多个字段组合值（键）排序的数按关系中指定的一个或多个字段组合值（键）排序的数据文件；据文件； 索引文件索引文件 为方便检索数据文件中元组，而建立的一个独立的辅助为方便检索数据文件中元组，而建立的一个独立的辅助文件或辅助关系；文件或辅助关系； 索引项或索引记录通常包含两个字段：键和指针；索引项或索引记录通常包含两个字段：键和指针； 索引表通常很小索引表通常很小; 按索引项（记录或元组）按索引项（记录或元组） 与关系中元组的对应方式，与关系中元组的对应方式，可将索引分为稠密索引和稀疏索引两类。可将索引分为稠密索引和稀疏索引两类。2022年6月13日62.1顺序文件上的索引顺序文件

4、上的索引稠密索引稠密索引 稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点 使用稠密索引文件的好处使用稠密索引文件的好处2022年6月13日7索引文件数据文件：元组按主键排序每个存储块只存放两个记录2.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引 稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点 是一个独立文件，占用系列存储块，块中仅存是一个独立文件，占用系列存储块，块中仅存放记录键和指向记录的指针；放记录键和指向记录的指针； 每个索引项对应相应数据文件中的一条记录；每个索引项对应相应数据文件中的一条记录

5、； 通常其大小要明显小于数据文件；通常其大小要明显小于数据文件； 稠密索引的查找稠密索引的查找 使用稠密索引文件的好处使用稠密索引文件的好处2022年6月13日82.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引 稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点 稠密索引的查找稠密索引的查找 支持按给定键值查找相应记录的查询支持按给定键值查找相应记录的查询 给定一个键值给定一个键值K （1）现在索引块中查找）现在索引块中查找K （2）找到）找到K后，按照后，按照K所对应的指针到数据文件中寻所对应的指针到数据文件中寻找相应的记录找相应的记录 使用稠密

6、索引文件的好处使用稠密索引文件的好处2022年6月13日92.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引 稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点 稠密索引的查找稠密索引的查找 使用稠密索引文件的好处使用稠密索引文件的好处 索引数据块通常比数据块少，索引数据块通常比数据块少，I/0次数少，如果索次数少，如果索引足够小，甚至可以将整个索引放在内存缓冲区引足够小，甚至可以将整个索引放在内存缓冲区中，则只需一次性读入索引的中，则只需一次性读入索引的I/O，就可以定位任，就可以定位任意的记录；意的记录； 由于索引文件中键被排序，可用二分法快速查

7、找，由于索引文件中键被排序，可用二分法快速查找，若有若有n个索引项，最多只需要查个索引项，最多只需要查log2n个块；个块；2022年6月13日102.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引 稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点2022年6月13日112.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引 稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点 为每个存储块设一个键为每个存储块设一个键-指针对指针对 键值是每个数据块中第一个记录的对应值键值是每个数据块中第一个记录的对应值 稀疏

8、索引的查找稀疏索引的查找 与稠密索引比较与稠密索引比较2022年6月13日122.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引 稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点 稀疏索引的查找稀疏索引的查找 找出键值为找出键值为K的记录的记录（1）在索引中查找键值小于或等于）在索引中查找键值小于或等于K的最大键值的最大键值（2）根据指针找到相应数据块）根据指针找到相应数据块（3）搜索数据块以找到键值为）搜索数据块以找到键值为K的记录的记录 与稠密索引比较与稠密索引比较2022年6月13日132.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引

9、稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点 稀疏索引的查找稀疏索引的查找 与稠密索引比较与稠密索引比较（1）节省了存储空间）节省了存储空间（2）查找给定值的记录需要更多时间）查找给定值的记录需要更多时间例：查询例：查询“是否存在键值为是否存在键值为K的记录？的记录？” 稠密索引只需考虑键稠密索引只需考虑键K在索引中的存在在索引中的存在 稀疏索引要执行稀疏索引要执行I/O操作去检索可能存在键值为操作去检索可能存在键值为K的记录的块的记录的块2022年6月13日142.1顺序文件上的索引顺序文件上的索引多级索引多级索引 在索引的基础上，再建索引在索引

10、的基础上，再建索引 2022年6月13日152.1顺序文件上的索引顺序文件上的索引多级索引多级索引 如对主索引再建立一级稀疏索引,即对每个索引块建立一个索引记录,就形成了二级索引此时外层索引块可常驻内存,在查找记录时内层索引块只要读1次就行 如果外层索引块的数目太多,不能全部进内存,那么可对最外层索引再外建一层索引,这就形成了多级索引技术。 二级以上索引肯定是稀疏索引；二级以上索引肯定是稀疏索引； 一级索引通常是稠密的；一级索引通常是稠密的； 多级索引的性能及管理的方便性不如多级索引的性能及管理的方便性不如B树结构；树结构；2022年6月13日162.2 辅助索引辅助索引 应用背景应用背景 在

11、实际的在实际的DB应用中，经常需要进行针对非主属性的应用中，经常需要进行针对非主属性的查询，为了加快查询的速度，也可以对非主属性建立查询，为了加快查询的速度，也可以对非主属性建立索引：索引： SELECT name, address FROM movieStar WHERE birthDate=DATE(1995-01-01)； 可在属性上建立索引：可在属性上建立索引： CREATE INDEX i_birthDate ON movieStar(birthDate) 相对与主键索引，我们称之为辅助索引。相对与主键索引，我们称之为辅助索引。 2022年6月13日172.2 辅助索引辅助索引 基本

12、特点与设计基本特点与设计辅助索引的特点辅助索引的特点可能存在重复键；可能存在重复键；数据文件一般不按辅助索引键排序；数据文件一般不按辅助索引键排序；辅助索引设计辅助索引设计必须是稠密的索引结构；必须是稠密的索引结构；索引文件中索引项按键值排序；索引文件中索引项按键值排序；可根据需要建立二级或多级索引可根据需要建立二级或多级索引存在空间浪费，如某个键在数据文件中出存在空间浪费，如某个键在数据文件中出现现n次，那么这个键值将在索引文件中出次，那么这个键值将在索引文件中出现现n次。次。2022年6月13日182.2 辅助索引辅助索引 基本特点与设计基本特点与设计 如果查找键的值的顺序与主文件的顺序不

13、一致,那么这种索引称为辅助索引,或非聚集索引。 辅助索引总是稠密索引，通常有重复值 辅助索引的索引项按键值排序 辅助索引的指针不是指向一个或几个连续存储块，而是指向很多不同的块。例：k=20 要查找两个索引块，还要访问指针指向的三个不同的数据块2022年6月13日192.2 辅助索引辅助索引 应用应用 堆文件（1）最基本最简单的文件结构 （2）记录不以任何顺序存放 （3）记录可能放在不邻接的块上 聚簇文件（1）RDB单关系上的聚簇-将记录按某个字段顺序排列在块中（2）RDB多关系上的聚簇-一个块中存储不同类型的记录 ，两个或多个关系的元组被混在一起2022年6月13日202.2 辅助索引辅助索

14、引 应用应用 顺序文件建立附加索引 堆结构的主索引文件 聚簇文件2022年6月13日212.2 辅助索引辅助索引 应用应用 聚簇文件例：Movie(title, year, length, studioname) Studio(name, address, president) SELECT president FROM Movie, Studio WHERE title=Star AND Movie. studioname= S 为了使此种连接效率更高，采用聚簇文件结构：关系Movie的元组和Studio的元组存放在相同的一系列块中，每个Studio元组后面存放关系Mov

15、ie中该制片厂的所有电影元组2022年6月13日222.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)2022年6月13日232.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)索引结构组织索引结构组织间接层的桶中只存放指针；间接层的桶中只存放指针；只要键值的总长度大于指针，就可以较好克只要键值的总长度大于指针，就可以较好克服一般辅助索引中的空间浪费现象；服一般辅助索引中的空间浪费现象；可以在不访问数据文件记录的前提下，利用可以在不访问数据文件记录的前提下，利用桶指针帮助问题以下一些问题：桶指针帮助问题以下一些问题：当查询有多个条件，且每个条件都有可用的索引当查询有多个条

16、件，且每个条件都有可用的索引时，可以通过在主存中时，可以通过在主存中对指针集合求交集对指针集合求交集，来找，来找出满足所有条件的记录，然后，只需检索交集中出满足所有条件的记录，然后，只需检索交集中指针指向的记录，从而节省了不必要的指针指向的记录，从而节省了不必要的I/O。2022年6月13日242.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶) 辅助索引可以采用上面的方法实现:仍然为每个查找键值建立一个索引记录,内容包括查找键值和一个指针,但这个指针不指向主文件中的记录,而是指向一个桶,桶内存放指向具有同一查找键值的主记录的指针。 如上图所示, 辅助索引的指针并不直接指向文件,而是

17、每个指针指向一个包含文件指针的存储桶，存储桶中的每个指针都指向文件中的记录。 使用桶介于辅助索引和数据文件之间，节约空间，避免键值重复。2022年6月13日252.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)2022年6月13日26可以通过在主存中对指针集合求交来找到满足所有条件的指针，只需要检索交集中指针指向的记录。SELECT titleFROM MovieWHERE studioname=Disney AND year=1995;2.3 数据文件修改期间的索引维护数据文件修改期间的索引维护 索引文件是顺序文件，到目前为止，索引文件是顺序文件，到目前为止，我们都假设数据文件和

18、索引文件由一我们都假设数据文件和索引文件由一些连续的、装满某种类型记录的存储些连续的、装满某种类型记录的存储块组成。块组成。 由于在实际应用中，总是需要不断地由于在实际应用中，总是需要不断地对数据进行插入、删除、修改，这势对数据进行插入、删除、修改，这势必会导致顺序文件这样的组织发生变必会导致顺序文件这样的组织发生变化和调整。化和调整。 2022年6月13日272.3 数据文件修改期间的索引维护数据文件修改期间的索引维护 当数据文件变化后，通常必须对索引文当数据文件变化后，通常必须对索引文件进行相应的调整，以适应数据文件的件进行相应的调整，以适应数据文件的变化；变化； 索引文件的调整可借鉴数据

19、文件中所用索引文件的调整可借鉴数据文件中所用的一些策略：的一些策略：2022年6月13日282.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点2022年6月13日29B树结构树结构B树查询树查询B树插入树插入B树删除树删除B树效率树效率 应用方式应用方式2.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点 m阶阶B树节点的子节点数约束树节点的子节点数约束 最大约束：每个节点至多有最大约束：每个节点至多有m个子节点；个子节点； 最少约束最少约束 根节点：最少要有两个子节点根节点：最少要有两个子节点 叶节点：可以没有子节点；叶节点：可以没有子节点； 内节点：至少有内节点：至少

20、有 m/2 子节点子节点 所有的叶节点都在同一层；所有的叶节点都在同一层； 非叶节点的键与指针非叶节点的键与指针 有有j个键的非叶节点，恰好包括个键的非叶节点，恰好包括j1个子节点指针个子节点指针 节点的形式：节点的形式：P0, K0, P1, K1, P2, K2, , Pj-1, Kj-1, Pj 将将B树扩展为树扩展为B+树，使之适合于树，使之适合于DB索引应用索引应用 每个叶节点至少有每个叶节点至少有 (m+1)/2 个指针指向数据记录；最后一个个指针指向数据记录；最后一个指针指向它右边的下一个右节点（最后指针指向它右边的下一个右节点（最后1个叶节点的最后个叶节点的最后1个个指针可为空

21、）；指针可为空）； 2022年6月13日30B树树2.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点 2022年6月13日31B树树2.4.2 基于基于B树的索引树的索引-B树的查找树的查找 归纳查找归纳查找 基础：若已经处于叶节点；基础：若已经处于叶节点；(则只需在结点内搜索则只需在结点内搜索) 归纳：若处于某内部节点，且它的键值为归纳：若处于某内部节点，且它的键值为 K1, K2, ,Kj-1； 如如kk1，第一个子节点；，第一个子节点； k1 = k k2 第第2个节点个节点 例：查找例：查找k=41的记录的记录2022年6月13日32 范围查找范围查找l只要先找到下限起点，

22、然后顺着找下去，直到找到只要先找到下限起点，然后顺着找下去，直到找到一个大于上限的键为止；一个大于上限的键为止；例：查找范围（例：查找范围（10，25）B树树2.4.3 基于基于B树的索引树的索引-B树的插入树的插入 定位合适的叶节点定位合适的叶节点(令为令为N)，如有空，插入即可结束，如有空，插入即可结束 如无空，在如无空，在N右边创建一个新的节点右边创建一个新的节点M，并按下面步，并按下面步骤进行调整安排：骤进行调整安排： 重排插入新键后重排插入新键后N中的键序，共中的键序，共 (n+1)个个 前前 (n+1)/2 个键指针对留在个键指针对留在N中，其它移入中，其它移入M中（至少有中（至少

23、有 (n+1)/2 个）个） M和和N中键指针对个数肯定都能满足约束条件！中键指针对个数肯定都能满足约束条件！ 转下一步：调整转下一步：调整N, M的上层父节点；的上层父节点； 调整调整N/M的上层父节点（的上层父节点（NP/MP） 递归调整递归调整NP/MP的上层节点，直到完成，必要时可能的上层节点，直到完成，必要时可能还要增加树的层数。还要增加树的层数。2022年6月13日33B树树2.4.3 基于基于B树的索引树的索引-B树的插入树的插入 调整调整M, N的上层节点的上层节点 在原在原N的父节点的父节点NP中插入一个新的键值指针对，重排中插入一个新的键值指针对，重排NP键值重调整键值重调

24、整NP的所有子结点指针；如键值数不超限，插入的所有子结点指针；如键值数不超限，插入结束；否则转下一步分裂结束；否则转下一步分裂NP ； 分裂分裂NP为为(NP, MP)，MP是新的紧靠是新的紧靠NP右边的兄弟节点；右边的兄弟节点； 前前 n+1/2 指针指针留在留在NP中；后中；后 n+1/2 指针指针移入移入MP中；中； 前前 n/2 个键保留在节点个键保留在节点NP中，后中，后 n/2 个键移到节点个键移到节点MP中，中间的中，中间的键键K会被结点会被结点NP和和MP的父结点用来划分在这两个结点之间的查找的父结点用来划分在这两个结点之间的查找 重计算重计算NP,MP中的键值，必要时调整中的

25、键值，必要时调整NP,MP的父节点（的父节点（N的祖父节的祖父节点），以正确划分点），以正确划分NP,MP中的键；中的键； 递归调整递归调整NP，MP的上层节点，直到完成，必要时可的上层节点，直到完成，必要时可能还需增加树的层数。能还需增加树的层数。 举例：在图举例：在图4-23中插入键值中插入键值402022年6月13日34B树树2.4.4 基于基于B树的索引树的索引-B树的删除树的删除 删除首先是查找定位，找到所在叶节点删除首先是查找定位，找到所在叶节点(令为令为N)后删除键指针对；后删除键指针对； 如删除后违反树约束，则需要进行相应调整如删除后违反树约束，则需要进行相应调整 若若N有有1

26、键指针对个数超过最小数的兄弟节点，键指针对个数超过最小数的兄弟节点，则直接从中借用一个，但会导致上层父节点需要则直接从中借用一个，但会导致上层父节点需要调整；调整； 若无兄弟节点可借，则可合并若无兄弟节点可借，则可合并N到它的一个兄弟到它的一个兄弟节点。这样，也可能会导致上层违反约束，则可节点。这样，也可能会导致上层违反约束，则可能要从远亲借一个近邻的表兄弟节点能要从远亲借一个近邻的表兄弟节点(整个节点整个节点) 沿树递归地删除；沿树递归地删除； 举例举例（在图（在图4-23中分别删除中分别删除7和和11,教材教材P120-121）2022年6月13日35B树树2.4.5 B树的特点与效率树的

27、特点与效率 能自动保持与数据文件大小相适应的索引层次；能自动保持与数据文件大小相适应的索引层次； 能对所使用的空间进行管理，使得每个块的充满度能对所使用的空间进行管理，使得每个块的充满度在半满与全满之间，索引不需要溢出块在半满与全满之间，索引不需要溢出块 读有读有B树索引的数据块的树索引的数据块的I/O次数次数B树的层数树的层数 1 当当B树阶数树阶数m很大时，插入很大时，插入/删除引起的调整大多限删除引起的调整大多限在叶子节点层，基本上可忽略在叶子节点层，基本上可忽略B数重组带来的数重组带来的I/O开开销；销； 可让可让B数的根结点永久驻留内存；把数的根结点永久驻留内存；把B数的第二层数的第

28、二层节点保存在主存缓冲区也是合理的；节点保存在主存缓冲区也是合理的；2022年6月13日36B树树2.4.6 B树的应用方式树的应用方式 查找键是主键，索引是稠密的；查找键是主键，索引是稠密的； 文件主键排序，文件主键排序，B树稀疏索引（每个数据树稀疏索引（每个数据块对应块对应B树叶节点的一个指针）；树叶节点的一个指针）； 用于非主键属性，且有重复键的情形（需用于非主键属性，且有重复键的情形（需修改内部节点的部分含义，引入修改内部节点的部分含义，引入最小新键最小新键的概念）。叶节点中为数据文件里出现的的概念）。叶节点中为数据文件里出现的每个属性值每个属性值K设有一个键设有一个键-指针对，其中指

29、指针对，其中指针指向排序键值为针指向排序键值为K的记录中的第一个。的记录中的第一个。2022年6月13日37B树树2. 5基于散列的索引基于散列的索引2.5.1 散列散列(hash)的数据结构的数据结构 散列函数及其选择原则散列函数及其选择原则要求要求:随机分布好、易计算随机分布好、易计算； 散列键（散列函数的参数）与散列值（散列散列键（散列函数的参数）与散列值（散列函数结果值）函数结果值） 维数为维数为B的的桶数组：桶数组：0B-1； 被散列对象将根据其键值，计算散列值，然被散列对象将根据其键值，计算散列值，然后保存到相应的桶中；后保存到相应的桶中； 桶内对象，按链连接起来，构成对象链。桶内

30、对象，按链连接起来，构成对象链。2022年6月13日382.5.1 散列散列(hash)的数据结构的数据结构2022年6月13日39keyh(key)可以是记录或指向记录的指针h(k)散列函数：以查找键为参数并计算出一个介于0-B-1的整数。k是整数-k/B的余数K是字符串-每个字符看成整数累加/B的余数2. 5.1辅存散列表（静态散列表）辅存散列表（静态散列表） 桶数组为一组存储块；桶数组为一组存储块； 散列的插入散列的插入:空间不够（桶溢出），可增加溢空间不够（桶溢出），可增加溢出链块；出链块； 散列删除，删除后如某溢出块空，则应删除散列删除，删除后如某溢出块空，则应删除相应的溢出块；相应

31、的溢出块； 辅存散列的效率辅存散列的效率 理想情况只需一次理想情况只需一次I/O； 非理想情况可能需要多次非理想情况可能需要多次I/O（存在对象链、溢出（存在对象链、溢出块链）；块链）；2022年6月13日402. 5.1辅存散列表（静态散列表）辅存散列表（静态散列表） 例：假定每个存储块只能存放2个记录 B=4散列函数h的返回值03之间键值为afh(d)=0 h(c)=h(e)=1 h(b)=2 h(a)=h(f)=3则记录在块中的分布如图所示2022年6月13日410123dcebaf链接溢出块2. 5.1辅存散列表（静态散列表）辅存散列表（静态散列表） 散列表的插入查找键为k的记录需要被

32、插入：(1) 计算h(k)(2) 如果桶号为h(k)的桶还有空间，把记录存放到此桶的存储块中(3)存储块没有空间时存储到块链上的某个溢出块中(4)如果桶的所有存储块都没有空间，增加一个新溢出块到该桶的链上，并把新记录存入该块例：增加一个键值为g的记录，且h(g)=1 把记录加到1号桶 增加一个新块，链到桶1的第1块上 键值为g的记录插入到这一块中2022年6月13日420123dcebafg2. 5.1辅存散列表（静态散列表）辅存散列表（静态散列表） 散列表索引的效率 理想情况是存储器有足够多的桶，使绝大多数桶都只由一个块组成，这样查询1次I/O，比稀疏索引、稠密索引、B+树好得多。 所以应设

33、法减少每个桶的块数静态散列表-通的数目B不变动态散列表-允许B改变，使B近似于： 记录总数/块中容纳记录数 目的：每个桶大约有一个存储块2022年6月13日432.5.2 可扩展的散列表可扩展的散列表 引入一个间接层做桶，桶中仅保存指针；引入一个间接层做桶，桶中仅保存指针； 指针桶数组能增长，它的长度为指针桶数组能增长，它的长度为2n，每次增长，每次增长nn+1，桶数组长度扩一倍；，桶数组长度扩一倍； 多个连续的桶可共享（共同指向）一个数据块，多个连续的桶可共享（共同指向）一个数据块，每个数据块中有一个小凸块标记资格位数每个数据块中有一个小凸块标记资格位数（j）；）； 散列的结果值散列的结果值

34、为为K位二进制数（位二进制数（K可达到可达到32位，足够位，足够!）；）； 实际用的桶编号位数实际用的桶编号位数 i = k,用用K的前的前(左边左边)i 位位 i 值作为结构一部分被保存；值作为结构一部分被保存；2022年6月13日44相对静态散列表的增强相对静态散列表的增强 2.5.2 可扩展的散列表可扩展的散列表2022年6月13日45i=10100011001110011例: (1)假定k=4,即h产生4位二进制序列；(2)使用位i=1，所以桶数组项：21=2项 （ 0，1）(3)桶数组的项指向二个块：l第一块存放当前所有查找键被散列成以0开头的二进制序列的记录l第二块存放所有查找键被

35、散列成以1开头的二进制序列的记录(4)为方便，显示的记录键是散列函数将这些键转换成的二进制位序列(5)每个存储块的“小凸块”显示1，表明由散列函数得到的位序列中有多少位用于确定记录在该块中的成员资格。j2.5.2 可扩展的散列表可扩展的散列表-插入插入 计算计算h(k)，并取结果（散列值）的前，并取结果（散列值）的前i位，根据它找到位，根据它找到桶及对应的存储块；桶及对应的存储块； 如存储块中有空间，插入即可，如无空间，按如下如存储块中有空间，插入即可，如无空间，按如下的两种情形处理：的两种情形处理：(1)资格位数资格位数ji 分裂存储块，然后根据散列值从左边算起的第分裂存储块，然后根据散列值

36、从左边算起的第j+1位的值，位的值，划分记录到分裂后的两个块中（划分记录到分裂后的两个块中（1放在在新块中，放在在新块中，=0放放在原块中）；在原块中）； 分裂后的两个块资格位分裂后的两个块资格位j均增加均增加1； 调整桶数组中的指针（针对新块）调整桶数组中的指针（针对新块）(2)资格位数资格位数ji ii+1，将桶数组扩大，将桶数组扩大1倍，新桶数组倍，新桶数组W0,W1指向原指向原W指向指向的块；的块； 按步骤按步骤(1)处理；处理； 2022年6月13日462.5.2 可扩展的散列表可扩展的散列表-操作示例操作示例2022年6月13日472.5.2 可扩展的散列表可扩展的散列表-操作示例

37、操作示例2022年6月13日482.5.2 可扩展的散列表可扩展的散列表-操作步骤操作步骤上例插入1010（1）第1位是1，属于第2个块（2）该块已满需要分裂（3）j=i=1 将桶数组加位i=2（4）根据第2位，为0：记录1001，1010划分到原块； 为1：记录1100划分到新块（5）分裂后的两个块成员资格位分裂后的两个块成员资格位j均增加均增加1变为变为2；（6）调整桶数组中的指针（针对新块）调整桶数组中的指针（针对新块）2022年6月13日492.5.2 可扩展的散列表可扩展的散列表-操作示例操作示例 插入键值分别为0000和0111的记录2022年6月13日50i=2000000010

38、111100110101100222200011011因为 j=1 i=2 jI 所以不用调整桶数组2.5.2 可扩展的散列表可扩展的散列表应用应用 优点好处：查找非常直接！优点好处：查找非常直接！ 查桶数组查桶数组+记录所在数据块内查找；记录所在数据块内查找； 桶数组通常驻留内存，实际只需桶数组通常驻留内存，实际只需1次次I/O; 存在问题存在问题 当桶数组翻倍时，要做大量的工作；当桶数组翻倍时，要做大量的工作； 翻倍后，主存可能放不下，会导致系统性能骤翻倍后，主存可能放不下，会导致系统性能骤然下降；然下降； 虽然记录不多，但因某些桶记录过分集中，可虽然记录不多，但因某些桶记录过分集中，可能

39、导致桶编号位数（能导致桶编号位数（i）很大，空桶过多；）很大，空桶过多； 例：例：i=20 j=20, j=3, j=10 记录总数远远小于记录总数远远小于2202022年6月13日512.5.3 线性散列线性散列结构特点结构特点 结构参数：桶数结构参数：桶数 n；桶编号位数；桶编号位数i；记录总数；记录总数r 桶数桶数 n ( 2n)，桶编号位数，桶编号位数 log2n i ，且从散列，且从散列值的右边（低位）取相应位；值的右边（低位）取相应位； 桶数桶数n增加缓慢，每插入一个记录，检查记录总增加缓慢，每插入一个记录，检查记录总数数r与桶数与桶数n的比值的比值r/n是否超过设定的上限，如是否

40、超过设定的上限，如超过则增加一个桶；超过则增加一个桶； n增加后，检查编号位增加后，检查编号位i是是否需要加大，如增加则原有桶编号高位用否需要加大，如增加则原有桶编号高位用0补齐补齐; 存储块并不总是可分裂（只有在增加一个桶时，存储块并不总是可分裂（只有在增加一个桶时，才会引起一次块分裂），因此，可增加溢出块；才会引起一次块分裂），因此，可增加溢出块； 结构参数与索引数据一同保存；结构参数与索引数据一同保存；2022年6月13日522.5.3 线性散列线性散列结构特点结构特点2022年6月13日5300001010111101i=1n=2r=3例1：图中二个桶：0，1 每个桶包含一个存储块 散

41、列值以0结尾的在0号桶 散列值以1结尾的在1号桶i-当前被使用的散列函数值的位数n-当前的桶数r-当前散列表中的记录总数规则-数据文件中的记录的个数 r=1.7n（桶的平均充满度不会 超过存储块容量的85%， r/2n=85%）2.5.3 线性散列线性散列插入记录插入记录 计算计算h(k)，并取散列值的后，并取散列值的后i位，令为位，令为 aiai-1a1；计算该数的二进制值为；计算该数的二进制值为m； 如如mn ，插入相应的桶或溢出块中；，插入相应的桶或溢出块中； 如如 n 指定上限，增加一个桶，令指定上限，增加一个桶，令桶号为桶号为ai1aia1值，并将该桶原先寄存在值，并将该桶原先寄存在

42、0aia1桶中的记录取回本桶。桶中的记录取回本桶。 如如n 2i，ii+1，所有原桶编号前补，所有原桶编号前补0；2022年6月13日542.5.3 线性散列线性散列插入记录举例插入记录举例2022年6月13日55例2：插入键值散列为0101的记录（1）位序列以1结尾，记录属于第二个桶（2）r/n = 4/2 1.7 n提高为3 2.5.3 线性散列线性散列插入记录举例插入记录举例2022年6月13日5623（3）=2所以桶：00，01，10（4）分裂桶00 0000在0桶 1010在10桶2.5.3 线性散列线性散列插入记录举例插入记录举例2022年6月13日57例3：增加键值散列为0001的记录（1）最后2位为：01，且01桶存在，把记录放在01桶中。（2）该桶块已满，增加一个溢出块（3）三个记录按散列键的数值顺序保存（4）r/n = 5/3 =1.51.7 创建1个编号为11的新桶（4