第2章一维索引组织结构课件

2024年7月12日1高级数据库课程高级数据库课程第第2章：一维索引组织结构章：一维索引组织结构 第一部分第一部分 数据库系统基础数据库系统基础第二部分第二部分 数据库的数据存储管理数据库的数据存储管理第三部分第三部分 数据库查询处理数据库查询处理引言引言 整个关系在储存中如何存储与表示？以整个关系在储存中如何存储与表示？以及怎样才能有效检索与定位？及怎样才能有效检索与定位？比如，如何回答象比如，如何回答象 SELECT*FROM R 这样一个简单查询？这样一个简单查询？2024年7月12日2引言引言我们可能不得不检索辅存中的我们可能不得不检索辅存中的与数据库与数据库文件对应的文件对应的每个存储块，且还得依赖块每个存储块，且还得依赖块首部中存在足够得信息来表明该块记录首部中存在足够得信息来表明该块记录从什么地方开始，块中记录属于什么关从什么地方开始，块中记录属于什么关系；系；有效的解决方案有效的解决方案采用索引结构采用索引结构；2024年7月12日3索引：索引：索引是一种数据结构，它以记录的特征（通常是一个或多个字段的值）为输入，并能“快速地”找出具有该特征的记录2024年7月12日4引言引言查找键-建立索引的字段索引方法（1）顺序文件上的简单索引（2）非排序文件上的辅助索引（3）B树,一种可以在任何文件上建立索引的常用方法（4）散列表2024年7月12日52.1顺序文件上的索引顺序文件上的索引相关概念相关概念数据文件数据文件存放一个关系所有元组数据的文件；存放一个关系所有元组数据的文件；顺序文件顺序文件按关系中指定的一个或多个字段组合值（键）排序的数按关系中指定的一个或多个字段组合值（键）排序的数据文件；据文件；索引文件索引文件为方便检索数据文件中元组，而建立的一个独立的辅助为方便检索数据文件中元组，而建立的一个独立的辅助文件或辅助关系；文件或辅助关系；索引项或索引记录通常包含两个字段：键和指针；索引项或索引记录通常包含两个字段：键和指针；索引表通常很小索引表通常很小;按索引项（记录或元组）按索引项（记录或元组）与关系中元组的对应方式，与关系中元组的对应方式，可将索引分为稠密索引和稀疏索引两类。可将索引分为稠密索引和稀疏索引两类。2024年7月12日62.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点使用稠密索引文件的好处使用稠密索引文件的好处2024年7月12日7索引文件数据文件：元组按主键排序每个存储块只存放两个记录2.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点是一个独立文件，占用系列存储块，块中仅存是一个独立文件，占用系列存储块，块中仅存放记录键和指向记录的指针；放记录键和指向记录的指针；每个索引项对应相应数据文件中的一条记录；每个索引项对应相应数据文件中的一条记录；通常其大小要明显小于数据文件；通常其大小要明显小于数据文件；稠密索引的查找稠密索引的查找使用稠密索引文件的好处使用稠密索引文件的好处2024年7月12日82.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点稠密索引的查找稠密索引的查找 支持按给定键值查找相应记录的查询支持按给定键值查找相应记录的查询 给定一个键值给定一个键值K （1）现在索引块中查找）现在索引块中查找K （2）找到）找到K后，按照后，按照K所对应的指针到数据文件中寻所对应的指针到数据文件中寻找相应的记录找相应的记录使用稠密索引文件的好处使用稠密索引文件的好处2024年7月12日92.1顺序文件上的索引顺序文件上的索引稠密索引稠密索引稠密索引的数据结构组织形式稠密索引的数据结构组织形式 稠密索引文件的特点稠密索引文件的特点稠密索引的查找稠密索引的查找使用稠密索引文件的好处使用稠密索引文件的好处索引数据块通常比数据块少，索引数据块通常比数据块少，I/0次数少，如果索次数少，如果索引足够小，甚至可以将整个索引放在内存缓冲区引足够小，甚至可以将整个索引放在内存缓冲区中，则只需一次性读入索引的中，则只需一次性读入索引的I/O，就可以定位任，就可以定位任意的记录；意的记录；由于索引文件中键被排序，可用二分法快速查找，由于索引文件中键被排序，可用二分法快速查找，若有若有n个索引项，最多只需要查个索引项，最多只需要查log2n个块；个块；2024年7月12日102.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点2024年7月12日112.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点为每个存储块设一个键为每个存储块设一个键-指针对指针对键值是每个数据块中第一个记录的对应值键值是每个数据块中第一个记录的对应值稀疏索引的查找稀疏索引的查找与稠密索引比较与稠密索引比较2024年7月12日122.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点稀疏索引的查找稀疏索引的查找 找出键值为找出键值为K的记录的记录（1）在索引中查找键值小于或等于）在索引中查找键值小于或等于K的最大键值的最大键值（2）根据指针找到相应数据块）根据指针找到相应数据块（3）搜索数据块以找到键值为）搜索数据块以找到键值为K的记录的记录与稠密索引比较与稠密索引比较2024年7月12日132.1顺序文件上的索引顺序文件上的索引稀疏索引稀疏索引稀疏索引的数据结构组织形式稀疏索引的数据结构组织形式 稀疏索引文件的特点稀疏索引文件的特点稀疏索引的查找稀疏索引的查找与稠密索引比较与稠密索引比较（1）节省了存储空间）节省了存储空间（2）查找给定值的记录需要更多时间）查找给定值的记录需要更多时间例：查询例：查询“是否存在键值为是否存在键值为K的记录？的记录？”稠密索引只需考虑键稠密索引只需考虑键K在索引中的存在在索引中的存在 稀疏索引要执行稀疏索引要执行I/O操作去检索可能存在键值为操作去检索可能存在键值为K的记录的的记录的块块2024年7月12日142.1顺序文件上的索引顺序文件上的索引多级索引多级索引在索引的基础上，再建索引在索引的基础上，再建索引 2024年7月12日152.1顺序文件上的索引顺序文件上的索引多级索引多级索引如对主索引再建立一级稀疏索引,即对每个索引块建立一个索引记录,就形成了二级索引此时外层索引块可常驻内存,在查找记录时内层索引块只要读1次就行如果外层索引块的数目太多,不能全部进内存,那么可对最外层索引再外建一层索引,这就形成了多级索引技术。二级以上索引肯定是稀疏索引；二级以上索引肯定是稀疏索引；一级索引通常是稠密的；一级索引通常是稠密的；多级索引的性能及管理的方便性不如多级索引的性能及管理的方便性不如B树结构；树结构；2024年7月12日162.2 辅助索引辅助索引 应用背景应用背景 在实际的在实际的DB应用中，经常需要进行针对非主属性的应用中，经常需要进行针对非主属性的查询，为了加快查询的速度，也可以对非主属性建立查询，为了加快查询的速度，也可以对非主属性建立索引：索引：SELECT name,address FROM movieStar WHERE birthDate=DATE(1995-01-01)；可在属性上建立索引：可在属性上建立索引：CREATE INDEX i_birthDate ON movieStar(birthDate)相对与主键索引，我们称之为辅助索引。相对与主键索引，我们称之为辅助索引。2024年7月12日172.2 辅助索引辅助索引 基本特点与设计基本特点与设计辅助索引的特点辅助索引的特点可能存在重复键；可能存在重复键；数据文件一般不按辅助索引键排序；数据文件一般不按辅助索引键排序；辅助索引设计辅助索引设计必须是稠密的索引结构；必须是稠密的索引结构；索引文件中索引项按键值排序；索引文件中索引项按键值排序；可根据需要建立二级或多级索引可根据需要建立二级或多级索引存在空间浪费，如某个键在数据文件中出存在空间浪费，如某个键在数据文件中出现现n次，那么这个键值将在索引文件中出现次，那么这个键值将在索引文件中出现n次。次。2024年7月12日182.2 辅助索引辅助索引 基本特点与设计基本特点与设计如果查找键的值的顺序与主文件的顺序不一致,那么这种索引称为辅助索引,或非聚集索引。辅助索引总是稠密索引，通常有重复值辅助索引的索引项按键值排序辅助索引的指针不是指向一个或几个连续存储块，而是指向很多不同的块。例：k=20 要查找两个索引块，还要访问指针指向的三个不同的数据块2024年7月12日192.2 辅助索引辅助索引 应用应用堆文件（1）最基本最简单的文件结构 （2）记录不以任何顺序存放 （3）记录可能放在不邻接的块上聚簇文件（1）RDB单关系上的聚簇-将记录按某个字段顺序排列在块中（2）RDB多关系上的聚簇-一个块中存储不同类型的记录，两个或多个关系的元组被混在一起2024年7月12日202.2 辅助索引辅助索引 应用应用顺序文件建立附加索引堆结构的主索引文件聚簇文件2024年7月12日212.2 辅助索引辅助索引 应用应用聚簇文件例：Movie(title,year,length,studioname)Studio(name,address,president)SELECT president FROM Movie,Studio WHERE title=Star AND Movie.studioname=Studio.name 为了使此种连接效率更高，采用聚簇文件结构：关系Movie的元组和Studio的元组存放在相同的一系列块中，每个Studio元组后面存放关系Movie中该制片厂的所有电影元组2024年7月12日222.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)2024年7月12日232.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)索引结构组织索引结构组织间接层的桶中只存放指针；间接层的桶中只存放指针；只要键值的总长度大于指针，就可以较好克只要键值的总长度大于指针，就可以较好克服一般辅助索引中的空间浪费现象；服一般辅助索引中的空间浪费现象；可以在不访问数据文件记录的前提下，利用可以在不访问数据文件记录的前提下，利用桶指针帮助问题以下一些问题：桶指针帮助问题以下一些问题：当查询有多个条件，且每个条件都有可用的索引当查询有多个条件，且每个条件都有可用的索引时，可以通过在主存中时，可以通过在主存中对指针集合求交集对指针集合求交集，来找，来找出满足所有条件的记录，然后，只需检索交集中出满足所有条件的记录，然后，只需检索交集中指针指向的记录，从而节省了不必要的指针指向的记录，从而节省了不必要的I/O。2024年7月12日242.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)辅助索引可以采用上面的方法实现:仍然为每个查找键值建立一个索引记录,内容包括查找键值和一个指针,但这个指针不指向主文件中的记录,而是指向一个桶,桶内存放指向具有同一查找键值的主记录的指针。如上图所示,辅助索引的指针并不直接指向文件,而是每个指针指向一个包含文件指针的存储桶，存储桶中的每个指针都指向文件中的记录。使用桶介于辅助索引和数据文件之间，节约空间，避免键值重复。2024年7月12日252.2 辅助索引辅助索引 应用间接索引层应用间接索引层(桶桶)2024年7月12日26可以通过在主存中对指针集合求交来找到满足所有条件的指针，只需要检索交集中指针指向的记录。SELECT titleFROM MovieWHERE studioname=Disney AND year=1995;2.3 数据文件修改期间的索引维护数据文件修改期间的索引维护 索引文件是顺序文件，到目前为止，索引文件是顺序文件，到目前为止，我们都假设数据文件和索引文件由一我们都假设数据文件和索引文件由一些连续的、装满某种类型记录的存储些连续的、装满某种类型记录的存储块组成。块组成。由于在实际应用中，总是需要不由于在实际应用中，总是需要不断地对数据进行插入、删除、修改，断地对数据进行插入、删除、修改，这势必会导致顺序文件这样的组织发这势必会导致顺序文件这样的组织发生变化和调整。生变化和调整。2024年7月12日272.3 数据文件修改期间的索引维护数据文件修改期间的索引维护当数据文件变化后，通常必须对索引文当数据文件变化后，通常必须对索引文件进行相应的调整，以适应数据文件的件进行相应的调整，以适应数据文件的变化；变化；索引文件的调整可借鉴数据文件中所用索引文件的调整可借鉴数据文件中所用的一些策略：的一些策略：2024年7月12日282.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点2024年7月12日29B树结构树结构B树查询树查询B树插入树插入B树删除树删除B树效率树效率 应用方式应用方式2.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点 m阶阶B树节点的子节点数约束树节点的子节点数约束 最大约束：每个节点至多有最大约束：每个节点至多有m个子节点；个子节点；最少约束最少约束根节点：最少要有两个子节点根节点：最少要有两个子节点叶节点：可以没有子节点；叶节点：可以没有子节点；内节点：至少有内节点：至少有 m/2 子节点子节点所有的叶节点都在同一层；所有的叶节点都在同一层；非叶节点的键与指针非叶节点的键与指针有有j个键的非叶节点，恰好包括个键的非叶节点，恰好包括j1个子节点指针个子节点指针 节点的形式：节点的形式：P0,K0,P1,K1,P2,K2,Pj-1,Kj-1,Pj 将将B树扩展为树扩展为B+树，使之适合于树，使之适合于DB索引应用索引应用每个叶节点至少有每个叶节点至少有(m+1)/2 个指针指向数据记录；最后一个个指针指向数据记录；最后一个指针指向它右边的下一个右节点（最后指针指向它右边的下一个右节点（最后1个叶节点的最后个叶节点的最后1个个指针可为空）；指针可为空）；2024年7月12日30B树树2.4 基于基于B树的索引树的索引-B树的结构特点树的结构特点 2024年7月12日31B树树2.4.2 基于基于B树的索引树的索引-B树的查找树的查找 归纳查找归纳查找基础：若已经处于叶节点；基础：若已经处于叶节点；(则只需在结点内搜索则只需在结点内搜索)归纳：若处于某内部节点，且它的键值为归纳：若处于某内部节点，且它的键值为 K1,K2,Kj-1；如如kk1，第一个子节点；，第一个子节点；k1=k k2 第第2个节点个节点 例：查找例：查找k=41的记录的记录2024年7月12日32 范围查找范围查找l只要先找到下限起点，然后顺着找下去，直到找到只要先找到下限起点，然后顺着找下去，直到找到一个大于上限的键为止；一个大于上限的键为止；例：查找范围（例：查找范围（10，25）B树树2.4.3 基于基于B树的索引树的索引-B树的插入树的插入定位合适的叶节点定位合适的叶节点(令为令为N)，如有空，插入即可结束，如有空，插入即可结束如无空，在如无空，在N右边创建一个新的节点右边创建一个新的节点M，并按下面步，并按下面步骤进行调整安排：骤进行调整安排：重排插入新键后重排插入新键后N中的键序，共中的键序，共 (n+1)个个前前(n+1)/2 个键指针对留在个键指针对留在N中，其它移入中，其它移入M中（至少有中（至少有(n+1)/2 个）个）M和和N中键指针对个数肯定都能满足约束条件！中键指针对个数肯定都能满足约束条件！转下一步：调整转下一步：调整N,M的上层父节点；的上层父节点；调整调整N/M的上层父节点（的上层父节点（NP/MP）递归调整递归调整NP/MP的上层节点，直到完成，必要时可能的上层节点，直到完成，必要时可能还要增加树的层数。还要增加树的层数。2024年7月12日33B树树2.4.3 基于基于B树的索引树的索引-B树的插入树的插入调整调整M,N的上层节点的上层节点在原在原N的父节点的父节点NP中插入一个新的键值指针对，重排中插入一个新的键值指针对，重排NP键值重调整键值重调整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中的键值，必要时调整中的键值，必要时调整NP,MP的父节点（的父节点（N的祖父节点）的祖父节点），以正确划分，以正确划分NP,MP中的键；中的键；递归调整递归调整NP，MP的上层节点，直到完成，必要时可的上层节点，直到完成，必要时可能还需增加树的层数。能还需增加树的层数。举例：在图举例：在图4-23中插入键值中插入键值402024年7月12日34B树树2.4.4 基于基于B树的索引树的索引-B树的删除树的删除删除首先是查找定位，找到所在叶节点删除首先是查找定位，找到所在叶节点(令为令为N)后删除键指针对；后删除键指针对；如删除后违反树约束，则需要进行相应调整如删除后违反树约束，则需要进行相应调整若若N有有1键指针对个数超过最小数的兄弟节点，键指针对个数超过最小数的兄弟节点，则直接从中借用一个，但会导致上层父节点需要则直接从中借用一个，但会导致上层父节点需要调整；调整；若无兄弟节点可借，则可合并若无兄弟节点可借，则可合并N到它的一个兄弟节到它的一个兄弟节点。这样，也可能会导致上层违反约束，则可能点。这样，也可能会导致上层违反约束，则可能要从远亲借一个近邻的表兄弟节点要从远亲借一个近邻的表兄弟节点(整个节点整个节点)沿树递归地删除；沿树递归地删除；举例举例（在图（在图4-23中分别删除中分别删除7和和11,教材教材P120-121）2024年7月12日35B树树2.4.5 B树的特点与效率树的特点与效率 能自动保持与数据文件大小相适应的索引层次；能自动保持与数据文件大小相适应的索引层次；能对所使用的空间进行管理，使得每个块的充满度能对所使用的空间进行管理，使得每个块的充满度在半满与全满之间，索引不需要溢出块在半满与全满之间，索引不需要溢出块读有读有B树索引的数据块的树索引的数据块的I/O次数次数B树的层数树的层数 1当当B树阶数树阶数m很大时，插入很大时，插入/删除引起的调整大多限删除引起的调整大多限在叶子节点层，基本上可忽略在叶子节点层，基本上可忽略B数重组带来的数重组带来的I/O开开销；销；可让可让B数的根结点永久驻留内存；把数的根结点永久驻留内存；把B数的第二层节数的第二层节点保存在主存缓冲区也是合理的；点保存在主存缓冲区也是合理的；2024年7月12日36B树树2.4.6 B树的应用方式树的应用方式 查找键是主键，索引是稠密的；查找键是主键，索引是稠密的；文件主键排序，文件主键排序，B树稀疏索引（每个数据树稀疏索引（每个数据块对应块对应B树叶节点的一个指针）；树叶节点的一个指针）；用于非主键属性，且有重复键的情形（需用于非主键属性，且有重复键的情形（需修改内部节点的部分含义，引入修改内部节点的部分含义，引入最小新键最小新键的概念）。叶节点中为数据文件里出现的的概念）。叶节点中为数据文件里出现的每个属性值每个属性值K设有一个键设有一个键-指针对，其中指指针对，其中指针指向排序键值为针指向排序键值为K的记录中的第一个。的记录中的第一个。2024年7月12日37B树树2.5基于散列的索引基于散列的索引2.5.1 散列散列(hash)的数据结构的数据结构 散列函数及其选择原则散列函数及其选择原则要求要求:随机分布好、易计算随机分布好、易计算；散列键（散列函数的参数）与散列值（散列散列键（散列函数的参数）与散列值（散列函数结果值）函数结果值）维数为维数为B的的桶数组：桶数组：0B-1；被散列对象将根据其键值，计算散列值，然被散列对象将根据其键值，计算散列值，然后保存到相应的桶中；后保存到相应的桶中；桶内对象，按链连接起来，构成对象链。桶内对象，按链连接起来，构成对象链。2024年7月12日382.5.1 散列散列(hash)的数据结构的数据结构2024年7月12日39keyh(key)可以是记录或指向记录的指针h(k)散列函数：以查找键为参数并计算出一个介于0-B-1的整数。k是整数-k/B的余数K是字符串-每个字符看成整数累加/B的余数2.5.1辅存散列表（静态散列表）辅存散列表（静态散列表）桶数组为一组存储块；桶数组为一组存储块；散列的插入散列的插入:空间不够（桶溢出），可增加溢空间不够（桶溢出），可增加溢出链块；出链块；散列删除，删除后如某溢出块空，则应删除散列删除，删除后如某溢出块空，则应删除相应的溢出块；相应的溢出块；辅存散列的效率辅存散列的效率理想情况只需一次理想情况只需一次I/O；非理想情况可能需要多次非理想情况可能需要多次I/O（存在对象链、溢出（存在对象链、溢出块链）；块链）；2024年7月12日402.5.1辅存散列表（静态散列表）辅存散列表（静态散列表）例：假定每个存储块只能存放2个记录 B=4散列函数h的返回值03之间键值为afh(d)=0 h(c)=h(e)=1 h(b)=2 h(a)=h(f)=3则记录在块中的分布如图所示2024年7月12日410123dcebaf链接溢出块2.5.1辅存散列表（静态散列表）辅存散列表（静态散列表）散列表的插入查找键为k的记录需要被插入：(1)计算h(k)(2)如果桶号为h(k)的桶还有空间，把记录存放到此桶的存储块中(3)存储块没有空间时存储到块链上的某个溢出块中(4)如果桶的所有存储块都没有空间，增加一个新溢出块到该桶的链上，并把新记录存入该块例：增加一个键值为g的记录，且h(g)=1 把记录加到1号桶 增加一个新块，链到桶1的第1块上 键值为g的记录插入到这一块中2024年7月12日420123dcebafg2.5.1辅存散列表（静态散列表）辅存散列表（静态散列表）散列表索引的效率理想情况是存储器有足够多的桶，使绝大多数桶都只由一个块组成，这样查询1次I/O，比稀疏索引、稠密索引、B+树好得多。所以应设法减少每个桶的块数静态散列表-通的数目B不变动态散列表-允许B改变，使B近似于：记录总数/块中容纳记录数 目的：每个桶大约有一个存储块2024年7月12日432.5.2 可扩展的散列表可扩展的散列表引入一个间接层做桶，桶中仅保存指针；引入一个间接层做桶，桶中仅保存指针；指针桶数组能增长，它的长度为指针桶数组能增长，它的长度为2n，每次增长，每次增长nn+1，桶数组长度扩一倍；，桶数组长度扩一倍；多个连续的桶可共享（共同指向）一个数据块，多个连续的桶可共享（共同指向）一个数据块，每个数据块中有一个小凸块标记资格位数每个数据块中有一个小凸块标记资格位数（j）；）；散列的结果值散列的结果值为为K位二进制数（位二进制数（K可达到可达到32位，足够位，足够!）；）；实际用的桶编号位数实际用的桶编号位数 i=k,用用K的前的前(左边左边)i 位位i 值作为结构一部分被保存；值作为结构一部分被保存；2024年7月12日44相对静态散列表的增强相对静态散列表的增强 2.5.2 可扩展的散列表可扩展的散列表2024年7月12日45i=10100011001110011例:(1)假定k=4,即h产生4位二进制序列；(2)使用位i=1，所以桶数组项：21=2项（0，1）(3)桶数组的项指向二个块：l第一块存放当前所有查找键被散列成以0开头的二进制序列的记录l第二块存放所有查找键被散列成以1开头的二进制序列的记录(4)为方便，显示的记录键是散列函数将这些键转换成的二进制位序列(5)每个存储块的“小凸块”显示1，表明由散列函数得到的位序列中有多少位用于确定记录在该块中的成员资格。j2.5.2 可扩展的散列表可扩展的散列表-插入插入 计算计算h(k)，并取结果（散列值）的前，并取结果（散列值）的前i位，根据它找到位，根据它找到桶及对应的存储块；桶及对应的存储块；如存储块中有空间，插入即可，如无空间，按如下的如存储块中有空间，插入即可，如无空间，按如下的两种情形处理：两种情形处理：(1)资格位数资格位数ji分裂存储块，然后根据散列值从左边算起的第分裂存储块，然后根据散列值从左边算起的第j+1位的值，位的值，划分记录到分裂后的两个块中（划分记录到分裂后的两个块中（1放在在新块中，放在在新块中，=0放在放在原块中）；原块中）；分裂后的两个块资格位分裂后的两个块资格位j均增加均增加1；调整桶数组中的指针（针对新块）调整桶数组中的指针（针对新块）(2)资格位数资格位数jiii+1，将桶数组扩大，将桶数组扩大1倍，新桶数组倍，新桶数组W0,W1指向原指向原W指向指向的块；的块；按步骤按步骤(1)处理；处理；2024年7月12日462.5.2 可扩展的散列表可扩展的散列表-操作示例操作示例2024年7月12日472.5.2 可扩展的散列表可扩展的散列表-操作示例操作示例2024年7月12日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）调整桶数组中的指针（针对新块）调整桶数组中的指针（针对新块）2024年7月12日492.5.2 可扩展的散列表可扩展的散列表-操作示例操作示例插入键值分别为0000和0111的记录2024年7月12日50i=2000000010111100110101100222200011011因为 j=1 i=2 jI 所以不用调整桶数组2.5.2 可扩展的散列表可扩展的散列表应用应用优点好处：查找非常直接！优点好处：查找非常直接！查桶数组查桶数组+记录所在数据块内查找；记录所在数据块内查找；桶数组通常驻留内存，实际只需桶数组通常驻留内存，实际只需1次次I/O;存在问题存在问题当桶数组翻倍时，要做大量的工作；当桶数组翻倍时，要做大量的工作；翻倍后，主存可能放不下，会导致系统性能骤然翻倍后，主存可能放不下，会导致系统性能骤然下降；下降；虽然记录不多，但因某些桶记录过分集中，可能虽然记录不多，但因某些桶记录过分集中，可能导致桶编号位数（导致桶编号位数（i）很大，空桶过多；）很大，空桶过多；例：例：i=20 j=20,j=3,j=10 记录总数远远小于记录总数远远小于2202024年7月12日512.5.3 线性散列线性散列结构特点结构特点结构参数：桶数结构参数：桶数 n；桶编号位数；桶编号位数i；记录总数；记录总数r桶数桶数 n(2n)，桶编号位数，桶编号位数 log2n i，且从散列，且从散列值的右边（低位）取相应位；值的右边（低位）取相应位；桶数桶数n增加缓慢，每插入一个记录，检查记录总增加缓慢，每插入一个记录，检查记录总数数r与桶数与桶数n的比值的比值r/n是否超过设定的上限，如是否超过设定的上限，如超过则增加一个桶；超过则增加一个桶；n增加后，检查编号位增加后，检查编号位i是是否需要加大，如增加则原有桶编号高位用否需要加大，如增加则原有桶编号高位用0补齐补齐;存储块并不总是可分裂（只有在增加一个桶时，存储块并不总是可分裂（只有在增加一个桶时，才会引起一次块分裂），因此，可增加溢出块；才会引起一次块分裂），因此，可增加溢出块；结构参数与索引数据一同保存；结构参数与索引数据一同保存；2024年7月12日522.5.3 线性散列线性散列结构特点结构特点2024年7月12日5300001010111101i=1n=2r=3例1：图中二个桶：0，1 每个桶包含一个存储块 散列值以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值，并将该桶原先寄存在值，并将该桶原先寄存在0aia1桶中的记录取回本桶。桶中的记录取回本桶。如如n 2i，ii+1，所有原桶编号前补，所有原桶编号前补0；2024年7月12日542.5.3 线性散列线性散列插入记录举例插入记录举例2024年7月12日55例2：插入键值散列为0101的记录（1）位序列以1结尾，记录属于第二个桶（2）r/n=4/2 1.7 n提高为3 2.5.3 线性散列线性散列插入记录举例插入记录举例2024年7月12日5623（3）=2所以桶：00，01，10（4）分裂桶00 0000在0桶 1010在10桶2.5.3 线性散列线性散列插入记录举例插入记录举例2024年7月12日57例3：增加键值散列为0001的记录（1）最后2位为：01，且01桶存在，把记录放在01桶中。（2）该桶块已满，增加一个溢出块（3）三个记录按散列键的数值顺序保存（4）r/n=5/3=1.51.7 创建1个编号为11的新桶（4）分裂01桶的4个记录：01桶（0001，0101）11桶（0111，1111）（5）删除01桶溢出块2024年7月12日5800000001010110100111111100011011i=2n=4r=6000000010101101001111111000110i=2n=3r=62.5.3 线性散列线性散列查询记录举例查询记录举例例5 查找散列键值为1010的记录(1)i=2 查后2位10，看成二进制整数m=2(2)m=n 则编号为11的桶不存在(3)把第1位改为0后重新定位到桶01中(4)查看桶01 不存在1011 查找失败2024年7月12日602.6 位图索引的组织结构位图索引的组织结构其基本原理是:假设一个表T中有n个元组，A为表中的一个属性，那么，属性A的一个简单位图索引是一个长度为n的位图矢量的集合，每一个位图矢量对应于属性A取值域中的一个值。如果第i个元组的在属性A上的取值为vi，那么对应于值vi的位图矢量在位置i的取值为1，否则为0;2024年7月12日612.6 位图索引的组织结构位图索引的组织结构例：在表例：在表T的属性的属性Gender建立位图索引建立位图索引 Gender M F F 0 1 M 1 0 F 0 1给定表的属性给定表的属性A，我们将，我们将A的基数的基数(Cardinality，即，即A中不同的中不同的值的个数值的个数)，记为，记为|A|。如果为。如果为A的每个值都建立这样的一个的每个值都建立这样的一个位图，这些位图就构成了位图，这些位图就构成了A上的位图索引。显然，属性上的位图索引。显然，属性A的的位图索引共有位图索引共有|A|个位图，每个位图的长度与个位图，每个位图的长度与A所在的表的所在的表的行数相等。我们将行数相等。我们将A上的位图索引记为上的位图索引记为BA，设，设vi是是A的一个的一个值，值，BA中与中与vi相对应的位图记为相对应的位图记为Bvi。2024年7月12日622.6位图索引的组织结构位图索引的组织结构Gender M F Dept a b c d F 0 1 a 1 0 0 0 M 1 0 c 0 0 1 0 F 0 1 d 0 0 0 1 利用位图索引计算查询时主要进行二进制运算。例如，设Dept和Gender，都是表T的属性，分别为它们建立了位图索引Bdept，Bgender 若查找在部门d工作(Dept=d)的女性职员(Gender=F)，则令B=BdeptdBgenderF，则B中为1的那些位所对应的记录即为所求。同样如果查询或为女性，或者在部门d的职员，则有B=BdeptdBgenderF，得到结果位图B后，B中为1的那些位所对应的记录即为所求。2024年7月12日632.6 位图索引的组织结构位图索引的组织结构10100110112JoeM3115Ram M5119SueF5112WooM42024年7月12日6400100 00001 00001 00010 lCustomers(custid,name,sex,rating)Sex custid name sex rating rating例：找出有多少男性客户的rating值为5将属性sex的第1个位向量和属性rating第5个位向量相与将结果向量中的1进行计数得到结果优点：使用位操作高效地完成查询。