第2章一维索引组织结构

2023年2月5日1高级数据库课程第2章：一维索引组织结构

第一部分数据库系统基础

第二部分数据库的数据存储管理

第三部分数据库查询处理引言

整个关系在储存中如何存储与表示？以及怎样才能有效检索与定位？比如，如何回答象

SELECT*FROMR

这样一个简单查询？2023年2月5日2引言我们可能不得不检索辅存中的与数据库文件对应的每个存储块，且还得依赖块首部中存在足够得信息来表明该块记录从什么地方开始，块中记录属于什么关系；有效的解决方案――－采用索引结构；2023年2月5日3索引：索引是一种数据结构，它以记录的特征（通常是一个或多个字段的值）为输入，并能“快速地”找出具有该特征的记录2023年2月5日4引言查找键---建立索引的字段索引方法（1）顺序文件上的简单索引（2）非排序文件上的辅助索引（3）B树,一种可以在任何文件上建立索引的常用方法（4）散列表2023年2月5日52.1顺序文件上的索引—相关概念数据文件存放一个关系所有元组数据的文件；顺序文件按关系中指定的一个或多个字段组合值（键）排序的数据文件；索引文件为方便检索数据文件中元组，而建立的一个独立的辅助文件或辅助关系；索引项或索引记录通常包含两个字段：键和指针；索引表通常很小;按索引项（记录或元组）与关系中元组的对应方式，可将索引分为稠密索引和稀疏索引两类。2023年2月5日62.1顺序文件上的索引—稠密索引稠密索引的数据结构组织形式

稠密索引文件的特点使用稠密索引文件的好处2023年2月5日7索引文件数据文件：元组按主键排序每个存储块只存放两个记录2.1顺序文件上的索引—稠密索引稠密索引的数据结构组织形式

稠密索引文件的特点是一个独立文件，占用系列存储块，块中仅存放记录键和指向记录的指针；每个索引项对应相应数据文件中的一条记录；通常其大小要明显小于数据文件；

稠密索引的查找使用稠密索引文件的好处2023年2月5日82.1顺序文件上的索引—稠密索引稠密索引的数据结构组织形式

稠密索引文件的特点稠密索引的查找

支持按给定键值查找相应记录的查询给定一个键值K

（1）现在索引块中查找K

（2）找到K后，按照K所对应的指针到数据文件中寻找相应的记录使用稠密索引文件的好处2023年2月5日92.1顺序文件上的索引—稠密索引稠密索引的数据结构组织形式

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

稀疏索引文件的特点2023年2月5日112.1顺序文件上的索引—稀疏索引稀疏索引的数据结构组织形式

稀疏索引文件的特点为每个存储块设一个键-指针对键值是每个数据块中第一个记录的对应值稀疏索引的查找与稠密索引比较2023年2月5日122.1顺序文件上的索引—稀疏索引稀疏索引的数据结构组织形式

稀疏索引文件的特点稀疏索引的查找

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

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

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

—应用背景

在实际的DB应用中，经常需要进行针对非主属性的查询，为了加快查询的速度，也可以对非主属性建立索引：

SELECTname,addressFROMmovieStarWHEREbirthDate=DATE(‘1995-01-01’)；可在属性上建立索引：

CREATEINDEXi_birthDateONmovieStar(birthDate)

相对与主键索引，我们称之为辅助索引。

2023年2月5日172.2辅助索引

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

—基本特点与设计如果查找键的值的顺序与主文件的顺序不一致,那么这种索引称为辅助索引,或非聚集索引。辅助索引总是稠密索引，通常有重复值辅助索引的索引项按键值排序辅助索引的指针不是指向一个或几个连续存储块，而是指向很多不同的块。例：k=20

要查找两个索引块，还要访问指针指向的三个不同的数据块2023年2月5日192.2辅助索引

—应用堆文件（1）最基本最简单的文件结构（2）记录不以任何顺序存放（3）记录可能放在不邻接的块上聚簇文件（1）RDB单关系上的聚簇---将记录按某个字段顺序排列在块中（2）RDB多关系上的聚簇----一个块中存储不同类型的记录，两个或多个关系的元组被混在一起2023年2月5日202.2辅助索引

—应用顺序文件建立附加索引堆结构的主索引文件聚簇文件2023年2月5日212.2辅助索引

—应用聚簇文件例：Movie(title,year,length,studioname)Studio(name,address,president)

SELECTpresidentFROMMovie,StudioWHEREtitle=‘Star’ANDMovie.studioname=S

为了使此种连接效率更高，采用聚簇文件结构：关系Movie的元组和Studio的元组存放在相同的一系列块中，每个Studio元组后面存放关系Movie中该制片厂的所有电影元组2023年2月5日222.2辅助索引

—应用间接索引层(桶)2023年2月5日232.2辅助索引

—应用间接索引层(桶)索引结构组织间接层的桶中只存放指针；只要键值的总长度大于指针，就可以较好克服一般辅助索引中的空间浪费现象；可以在不访问数据文件记录的前提下，利用桶指针帮助问题以下一些问题：当查询有多个条件，且每个条件都有可用的索引时，可以通过在主存中对指针集合求交集，来找出满足所有条件的记录，然后，只需检索交集中指针指向的记录，从而节省了不必要的I/O。2023年2月5日242.2辅助索引

—应用间接索引层(桶)辅助索引可以采用上面的方法实现:仍然为每个查找键值建立一个索引记录,内容包括查找键值和一个指针,但这个指针不指向主文件中的记录,而是指向一个桶,桶内存放指向具有同一查找键值的主记录的指针。如上图所示,辅助索引的指针并不直接指向文件,而是每个指针指向一个包含文件指针的存储桶，存储桶中的每个指针都指向文件中的记录。使用桶介于辅助索引和数据文件之间，节约空间，避免键值重复。2023年2月5日252.2辅助索引

—应用间接索引层(桶)2023年2月5日26可以通过在主存中对指针集合求交来找到满足所有条件的指针，只需要检索交集中指针指向的记录。SELECTtitleFROMMovieWHEREstudioname=‘Disney’ANDyear=1995;2.3数据文件修改期间的索引维护

索引文件是顺序文件，到目前为止，我们都假设数据文件和索引文件由一些连续的、装满某种类型记录的存储块组成。由于在实际应用中，总是需要不断地对数据进行插入、删除、修改，这势必会导致顺序文件这样的组织发生变化和调整。2023年2月5日272.3数据文件修改期间的索引维护当数据文件变化后，通常必须对索引文件进行相应的调整，以适应数据文件的变化；索引文件的调整可借鉴数据文件中所用的一些策略：2023年2月5日282.4基于B树的索引--B树的结构特点2023年2月5日29B树结构B树查询B树插入B树删除B树效率应用方式2.4基于B树的索引--B树的结构特点

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

2023年2月5日30B树2.4基于B树的索引--B树的结构特点

2023年2月5日31B树2.4.2基于B树的索引--B树的查找

归纳查找基础：若已经处于叶节点；(则只需在结点内搜索)归纳：若处于某内部节点，且它的键值为

K1,K2,…,Kj-1；如k<k1，第一个子节点；k1=<k<k2

第2个节点…例：查找k=41的记录2023年2月5日32

范围查找只要先找到下限起点，然后顺着找下去，直到找到一个大于上限的键为止；例：查找范围（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的上层节点，直到完成，必要时可能还要增加树的层数。2023年2月5日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中插入键值402023年2月5日34B树2.4.4基于B树的索引--B树的删除删除首先是查找定位，找到所在叶节点(令为N)后删除键－指针对；如删除后违反树约束，则需要进行相应调整若N有1键－指针对个数超过最小数的兄弟节点，则直接从中借用一个，但会导致上层父节点需要调整；若无兄弟节点可借，则可合并N到它的一个兄弟节点。这样，也可能会导致上层违反约束，则可能要从远亲借一个近邻的表兄弟节点(整个节点)沿树递归地删除；举例（在图4-23中分别删除7和11,教材P120-121）2023年2月5日35B树2.4.5

B树的特点与效率

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

B树的应用方式

查找键是主键，索引是稠密的；文件主键排序，B树稀疏索引（每个数据块对应B树叶节点的一个指针）；用于非主键属性，且有重复键的情形（需修改内部节点的部分含义，引入最小新键的概念）。叶节点中为数据文件里出现的每个属性值K设有一个键-指针对，其中指针指向排序键值为K的记录中的第一个。2023年2月5日37B树2.5基于散列的索引

2.5.1散列(hash)的数据结构

散列函数及其选择原则要求:随机分布好、易计算；散列键（散列函数的参数）与散列值（散列函数结果值）维数为B的桶数组：0～B-1；被散列对象将根据其键值，计算散列值，然后保存到相应的桶中；桶内对象，按链连接起来，构成对象链。2023年2月5日382.5.1散列(hash)的数据结构2023年2月5日39key→h(key)<key>可以是记录或指向记录的指针h(k)散列函数：以查找键为参数并计算出一个介于0----B-1的整数。k是整数--------k/B的余数K是字符串---每个字符看成整数累加/B的余数2.5.1辅存散列表（静态散列表）

桶数组为一组存储块；散列的插入:空间不够（桶溢出），可增加溢出链块；散列删除，删除后如某溢出块空，则应删除相应的溢出块；辅存散列的效率理想情况只需一次I/O；非理想情况可能需要多次I/O（存在对象链、溢出块链）；2023年2月5日402.5.1辅存散列表（静态散列表）例：假定每个存储块只能存放2个记录

B=4散列函数h的返回值0~3之间键值为a~fh(d)=0h(c)=h(e)=1h(b)=2h(a)=h(f)=3则记录在块中的分布如图所示2023年2月5日410123dcebaf链接溢出块2.5.1辅存散列表（静态散列表）散列表的插入查找键为k的记录需要被插入：(1)计算h(k)(2)如果桶号为h(k)的桶还有空间，把记录存放到此桶的存储块中(3)存储块没有空间时存储到块链上的某个溢出块中(4)如果桶的所有存储块都没有空间，增加一个新溢出块到该桶的链上，并把新记录存入该块例：增加一个键值为g的记录，且h(g)=1

把记录加到1号桶增加一个新块，链到桶1的第1块上键值为g的记录插入到这一块中2023年2月5日420123dcebafg2.5.1辅存散列表（静态散列表）散列表索引的效率理想情况是存储器有足够多的桶，使绝大多数桶都只由一个块组成，这样查询1次I/O，比稀疏索引、稠密索引、B+树好得多。所以应设法减少每个桶的块数静态散列表----通的数目B不变动态散列表----允许B改变，使B近似于：记录总数/块中容纳记录数目的：每个桶大约有一个存储块2023年2月5日432.5.2可扩展的散列表引入一个间接层做桶，桶中仅保存指针；指针桶数组能增长，它的长度为2n，每次增长nn+1，桶数组长度扩一倍；多个连续的桶可共享（共同指向）一个数据块，每个数据块中有一个小凸块标记资格位数（j）；散列的结果值――为K位二进制数（K可达到32位，足够!）；实际用的桶编号位数i<=k,用K的前(左边)i位i值作为结构一部分被保存；2023年2月5日44相对静态散列表的增强

2.5.2可扩展的散列表2023年2月5日45i=10100011001110011例:(1)假定k=4,即h产生4位二进制序列；(2)使用位i=1，所以桶数组项：21=2项（0，1）(3)桶数组的项指向二个块：第一块存放当前所有查找键被散列成以0开头的二进制序列的记录第二块存放所有查找键被散列成以1开头的二进制序列的记录(4)为方便，显示的记录键是散列函数将这些键转换成的二进制位序列(5)每个存储块的“小凸块”显示1，表明由散列函数得到的位序列中有多少位用于确定记录在该块中的成员资格。j2.5.2可扩展的散列表--插入

计算h(k)，并取结果（散列值）的前i位，根据它找到桶及对应的存储块；如存储块中有空间，插入即可，如无空间，按如下的两种情形处理：(1)资格位数j<i分裂存储块，然后根据散列值从左边算起的第j+1位的值，划分记录到分裂后的两个块中（＝1放在在新块中，=0放在原块中）；分裂后的两个块资格位j均增加1；调整桶数组中的指针（针对新块）(2)资格位数j＝iii+1，将桶数组扩大1倍，新桶数组W0,W1指向原W指向的块；按步骤(1)处理；

2023年2月5日462.5.2可扩展的散列表--操作示例2023年2月5日472.5.2可扩展的散列表--操作示例2023年2月5日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）调整桶数组中的指针（针对新块）2023年2月5日492.5.2可扩展的散列表--操作示例插入键值分别为0000和0111的记录2023年2月5日50i=2000000010111100110101100222200011011因为j=1i=2j<I所以不用调整桶数组2.5.2可扩展的散列表—应用优点好处：查找非常直接！查桶数组+记录所在数据块内查找；桶数组通常驻留内存，实际只需1次I/O;存在问题当桶数组翻倍时，要做大量的工作；翻倍后，主存可能放不下，会导致系统性能骤然下降；虽然记录不多，但因某些桶记录过分集中，可能导致桶编号位数（i）很大，空桶过多；例：i=20j=20,j=3,j=10

记录总数远远小于2202023年2月5日512.5.3线性散列—结构特点结构参数：桶数n；桶编号位数i；记录总数r桶数n(<2n)，桶编号位数log2n＝i，且从散列值的右边（低位）取相应位；桶数n增加缓慢，每插入一个记录，检查记录总数r与桶数n的比值r/n是否超过设定的上限，如超过则增加一个桶；n增加后，检查编号位i是否需要加大，如增加则原有桶编号高位用0补齐;存储块并不总是可分裂（只有在增加一个桶时，才会引起一次块分裂），因此，可增加溢出块；结构参数与索引数据一同保存；2023年2月5日522.5.3线性散列—结构特点2023年2月5日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-1…a1；计算该数的二进制值为m；如m<n，插入相应的桶或溢出块中；如n<m，则把记录插入（寄存）到ai-1…a1值对应的块或溢出块中；计算r/n，如r/n>指定上限，增加一个桶，令桶号为ai＋1ai…a1值，并将该桶原先寄存在0ai…a1桶中的记录取回本桶。如n>2i，ii+1，所有原桶编号前补0；2023年2月5日542.5.3线性散列—插入记录举例2023年2月5日55例2：插入键值散列为0101的记录（1）位序列以1结尾，记录属于第二个桶（2）r/n=4/2>1.7n提高为32.5.3线性散列—插入记录举例2023年2月5日56㏒23（3）=2所以桶：00，01，10（4）分裂桶00

0000在0桶

1010在10桶2.5.3线性散列—插入记录举例2023年2月5日57例3：增加键值散列为0001的记录（1）最后2位为：01，且01桶存在，把记录放在01桶中。（2）该桶块已满，增加一个溢出块（3）三个记录按散列键的数值顺序保存（4）r/n=5/3=1.5<1.7不需要创建新桶2.5.3线性散列—插入记录举例例4插入键值散列为0111的记录（1）最后2位为11，但桶11不存在（2）把记录改为存入01桶，新记录存入该桶溢出块中（3）r/n=6/3=2>1.7创建1个编号为11的新桶（4）分裂01桶的4个记录：

01桶（0001，0101）

11桶（0111，1111）（5）删除01桶溢出块2023年2月5日5800000001010110100111111100011011i=2n=4r=6000000010101101001111111000110i=2n=3r=62.5.3线性散列—查询记录举例例5查找散列键值为1010的记录(1)i=2查后2位10，看成二进制整数m=2(2)m<n则编号为10的桶存在，到该桶中查找(3)检查记录的整个键来确定是否所需记录2023年2月5日592.5.3线性散列—查询记录举例例6查找散列键值为1011的记录(1)i=2查后2位11，看成二进制整数m=3(2)m>=n则编号为11的桶不存在(3)把第1位改为0后重新定位到桶01中(4)查看桶01不存在1011查找失败2023年2月5日602.6位图索引的组织结构其基本原理是:

假设一个表T中有n个元组，A为表中的一个属性，那么，属性A的一个简单位图索引是一个长度为n的位图矢量的集合，每一个位图矢量对应于属性A取值域中的一个值。如果第i个元组的在属性A上的取值为vi，那么对应于值vi