《RDBMS的物理组织》PPT课件.ppt

《《RDBMS的物理组织》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《RDBMS的物理组织》PPT课件.ppt（277页珍藏版）》请在金锄头文库上搜索。

1、第二章第二章RDBMS的物理组织的物理组织1第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE和和TeraData的数据库结构和体系结构的数据库结构和体系结构22.1存储介质存储介质l几类存储器几类存储器高速缓冲存储器（高速缓冲存储器（cache）主存储器主存储器(mainmemory)快擦写存储器快擦写存储器(flashmemory)磁盘存储器磁盘存储器(magnetic-diskstorage)光存储器光存储器(opticalstora

2、ge)磁带存储器磁带存储器(tapestorage)34第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE和和TeraData的数据库结构和体系结构的数据库结构和体系结构52.2存储方式存储方式l以文件方式存储以文件方式存储一个对象对应一个文件一个对象对应一个文件l存储管理交由存储管理交由OS整个整个DB对应一个或若干个文件对应一个或若干个文件l由由RDBMS进行存储管理进行存储管理6存储方式存储方式l大型大型RDBMS的存储方式的存储方式

3、DB通通常常被被划划分分成成更更小小的的单单位位，例例如如段段(Segment或或Area)，以增加灵活性以增加灵活性整整个个DB对对应应一一个个或或若若干干个个文文件件，由由DBMS进进行行存存储储管理管理不同不同RDBMS划分方法不同划分方法不同l示例：示例：ORACLE7示例：示例：ORACLE的存储方式的存储方式l表空间表空间(逻辑设备逻辑设备)对应磁盘上一个或多个物理数据文件对应磁盘上一个或多个物理数据文件可可以以有有多多个个表表空空间间，逻逻辑辑地地和和物物理理地地组组织织数数据据库库中中的数据存储。的数据存储。系系统统表表空空间间、联联机机表表空空间间、脱脱机机表表空空间间、永永

4、久久表表空空间、临时表空间间、临时表空间l数据文件数据文件8l段段由多个区间组成。由多个区间组成。数据段、索引段、数据段、索引段、LONG段、回滚段、临时段等段、回滚段、临时段等l区间区间由一组连续的数据块组成由一组连续的数据块组成l数据块数据块ORACLE数据库的磁盘存取单元数据库的磁盘存取单元数据块的大小必须等于服务器操作系统块的大小或数据块的大小必须等于服务器操作系统块的大小或倍数倍数9大型大型RDBMS的存储方式的存储方式划分数据库的好处：划分数据库的好处：l便于将数据库按联机存储和脱机存储来划分便于将数据库按联机存储和脱机存储来划分l便于动态地、模块地分配不同类型的存储区便于动态地、

5、模块地分配不同类型的存储区l便于数据的物理恢复便于数据的物理恢复l便于有效地封锁便于有效地封锁l便于处理数据安全便于处理数据安全10第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE的数据库结构和体系结构的数据库结构和体系结构11 Torepresent:lInteger(short):2bytese.g.,35is0000000000100011 Real,floatingpointnbitsformantissa,mforexponen

6、t.12 lCharactersvariouscodingschemessuggested,mostpopularisasciiTorepresent:Example:A:1000001a:11000015:0110101LF:000101013 lBooleane.g.,TRUE FALSE1111 11110000 0000Torepresent: Applicationspecifice.g.,RED1 GREEN3BLUE2YELLOW414 lDatese.g.:-Integer,#dayssinceJan1,1900-8characters,YYYYMMDD-7characters

7、,YYYYDDDlTimee.g.-Integer,secondssincemidnight-characters,HHMMSSFFTorepresent:15 lStringofcharactersNullterminatede.g.,Lengthgivene.g.,-Fixedlengthctacta3Torepresent:16 lBagofbitsLengthBitsTorepresent:17 KeyPoint FixedlengthitemsVariablelengthitems-usuallylengthgivenatbeginning18 lTypeofanitem:Tells

8、ushowtointerpret(plussizeiffixed)Also19第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE和和TeraData的数据库结构和体系结构的数据库结构和体系结构202.4数据组织方式数据组织方式l2.4.1数据组织方法概述数据组织方法概述l2.4.2记录记录l2.4.3块块l2.4.4增删改记录增删改记录212.4.1数据组织方法概述数据组织方法概述l字段字段-记录记录-块块-文件文件222.4数据组织方式数

9、据组织方式l2.4.1数据组织方法概述数据组织方法概述l2.4.2记录记录l2.4.3块块l2.4.4增删改记录增删改记录232.4.2记录记录l主要内容主要内容定长记录定长记录变长记录变长记录241.定长记录定长记录l1 1）定长记录的构造）定长记录的构造例：例：CREATETABLEMovieStar(Namechar(30)primarykey,Addressvarchar(255),Genderchar(1),Birthdatedate);2526某些机器对内存中数据地址的要求某些机器对内存中数据地址的要求l有有些些机机器器可可以以对对内内存存中中地地址址为为4的的倍倍数数的的字字节节

10、开开始始的的数数据据进进行行更更有有效效的的读读写写(64位位处处理理器器时时则则为为8的的倍数倍数)l在在某某些些机机器器上上，整整数数等等数数据据类类型型要要求求必必须须从从4的的倍倍数的地址处开始数的地址处开始l在某些机器上，双精度实数要求从在某些机器上，双精度实数要求从8的倍数处开始的倍数处开始 运行于这些机器上的运行于这些机器上的DBMS，转换字段在块内的偏转换字段在块内的偏移量时必须小心。移量时必须小心。27为简化地址转换，并提高可移植性，可规定为简化地址转换，并提高可移植性，可规定l每一条记录在块内从每一条记录在块内从4的倍数的字节处开始的倍数的字节处开始l记录中所有的字段都从与

11、记录偏移量为记录中所有的字段都从与记录偏移量为4的倍数的的倍数的字节处开始字节处开始28 l2）记录首部记录首部记录首部信息通常包括以下内容记录首部信息通常包括以下内容: :l记录模式记录模式l记录长度记录长度l时间戳时间戳29 记录模式记录模式l通常是指向通常是指向DBMS中存储该类记录模式的位置中存储该类记录模式的位置(数据数据字典字典)的一个指针的一个指针l模式信息模式信息关系的属性关系的属性属性类型属性类型属性在元组中出现的顺序属性在元组中出现的顺序属性或关系自身上的约束属性或关系自身上的约束(主码、完整性约束等主码、完整性约束等)30 记录长度记录长度时间戳时间戳l指明记录最后一次被

12、修改或被读的时间以及其他指明记录最后一次被修改或被读的时间以及其他可能的信息记录模式可能的信息记录模式312.变变长记录长记录1) )具有变长字段的记录具有变长字段的记录( (3种表示策略种表示策略) )变长字段前加长度变长字段前加长度 32先放定长字段，后放变长字段先放定长字段，后放变长字段33变长字段单独存放在一个块中变长字段单独存放在一个块中 34 2) )具有重复字段的记录具有重复字段的记录 ( (3种表示策略种表示策略) )将重复字段放在一起，在记录首部用指针指向每个重将重复字段放在一起，在记录首部用指针指向每个重复字段的第一次出现。复字段的第一次出现。 例：对于记录：姓名，地址，出

13、演过的影片指针例：对于记录：姓名，地址，出演过的影片指针 35变长字段及重复字段单独存放在一个块中变长字段及重复字段单独存放在一个块中 36折衷方案折衷方案在记录的定长部分预留足够空间，存储下列信息：在记录的定长部分预留足够空间，存储下列信息：l重复字段合理的出现次数重复字段合理的出现次数l指向可以找到这个重复字段其他出现的地方的指针指向可以找到这个重复字段其他出现的地方的指针l其他出现的次数其他出现的次数 373可变格式记录可变格式记录l可变格式记录的用途可变格式记录的用途 不同信息源集成。通过只列出非空字段来节省空间。不同信息源集成。通过只列出非空字段来节省空间。具有非常灵活的模式的记录。

14、如一条记录的许多字段具有非常灵活的模式的记录。如一条记录的许多字段会重复或根本不出现会重复或根本不出现l实现策略：自描述实现策略：自描述38392.4数据组织方式数据组织方式l2.4.1数据组织方法概述数据组织方法概述l2.4.2记录记录l2.4.3块块l2.4.4增删改记录增删改记录402.4.3块块l主要内容主要内容块和记录块和记录地址地址的表示的表示l普通记录地址普通记录地址l索引结构索引结构记录在块中的记录在块中的存储方式存储方式BOLB412.4.3块块l主要内容主要内容F块和记录块和记录地址地址的表示的表示l普通记录地址普通记录地址l索引结构索引结构记录在块中的记录在块中的存储方式

15、存储方式BOLB42一、块和记录地址的表示一、块和记录地址的表示l普通记录的地址普通记录的地址l索引结构（含指针）索引结构（含指针）431. 1. 普通记录的地址普通记录的地址l两种方式两种方式物理地址与逻辑地址物理地址与逻辑地址分别编址分别编址逻辑地址与物理地址逻辑地址与物理地址组合组合44(1)物理地址与逻辑地址分别编址物理地址与逻辑地址分别编址l逻辑地址到物理地址的映射：映射表逻辑地址到物理地址的映射：映射表l映射表为全程表映射表为全程表l移动记录和删除记录时不方便，必须修改映射表移动记录和删除记录时不方便，必须修改映射表4546(2)逻辑地址与物理地址组合逻辑地址与物理地址组合l是结构

16、化的地址模式是结构化的地址模式l两种组合方式两种组合方式块的物理地址块的物理地址+被访问记录的码值被访问记录的码值在每一个块内存储一个偏移量表在每一个块内存储一个偏移量表47块的物理地址块的物理地址+被访问记录的码值被访问记录的码值l使使用用物物理理地地址址部部分分找找到到包包含含所所查查记记录录的的块块，然然后后检查块内记录以找到具有指定码值的记录检查块内记录以找到具有指定码值的记录l查找效率不算好查找效率不算好48在每一个块内存储一个偏移量表在每一个块内存储一个偏移量表l记录的地址记录的地址块块的的物物理理地地址址加加上上该该记记录录在在此此块块的的偏偏移移量量表表项项中中的的偏移量偏移量

17、l可以在块内移动记录可以在块内移动记录只只需需改改变变记记录录在在偏偏移移量量表表中中的的表表项项，指指向向这这条条记记录录的指针仍能找到它。的指针仍能找到它。l如如果果偏偏移移量量表表项项足足够够大大，能能存存储储这这条条记记录录的的“转转向向地地址址”，则可以允许记录移到另一块，则可以允许记录移到另一块l如果记录被删除，可以在偏移量表项中置删除标记如果记录被删除，可以在偏移量表项中置删除标记4950512. 2. 索引结构（含指针）索引结构（含指针）l问题问题块在主存与二级存储器之间移动时，如何管理指针块在主存与二级存储器之间移动时，如何管理指针数据库地址：数据库地址：8B左右左右内存地址

18、：内存地址：4Bl方法方法映射表方法映射表方法指针混写方法指针混写方法 52映射表方法映射表方法53映射表方法映射表方法l优点：记录不被固定在内存优点：记录不被固定在内存l缺点：将数据库地址重复转换成内存地址缺点：将数据库地址重复转换成内存地址54指针混写方法指针混写方法l基本思想基本思想块从第二级存储器移到内存中时，将数据库地址空间块从第二级存储器移到内存中时，将数据库地址空间转换为虚拟地址空间。因此一个指针包含：转换为虚拟地址空间。因此一个指针包含：l一一个个二二进进制制位位，指指明明指指针针目目前前是是数数据据库库地地址址还还是是混写的内存地址混写的内存地址l数据库或内存指针数据库或内存

19、指针示例示例5556l混写指针的策略：根据混写指针的时机混写指针的策略：根据混写指针的时机自动混写自动混写按需混写按需混写显式控制显式控制571）自动混写自动混写l什么是自动混写什么是自动混写块块读入内存读入内存，即为它的所有指针和地址定位。，即为它的所有指针和地址定位。l如如果果地地址址A已已存存在在于于转转换换表表中中，则则用用相相应应的的内内存存地地址址代代替替刚刚移移进进内内存存中中的的块块中中的的A，并并将将“混混写写”位位置置1l如果如果A不在转换表中，仍保持为数据库指针不在转换表中，仍保持为数据库指针检索检索至指针至指针A时，如果其为数据库指针，则查找转换表，时，如果其为数据库指

20、针，则查找转换表，看数据库地址看数据库地址A当前是否有相应的内存地址，有则代替。当前是否有相应的内存地址，有则代替。没有，则将相应块读入内存缓冲区，并用相应内存地没有，则将相应块读入内存缓冲区，并用相应内存地址代替址代替A（混写），同时将其放入转换表。混写），同时将其放入转换表。58l自动混写的特点自动混写的特点当当块块被被装装载载进进内内存存时时，即即试试图图快快速速、有有效效地地混混写写所所有有指针。指针。一次混写所有可混写的指针，可能会节省时间一次混写所有可混写的指针，可能会节省时间其中一些指针可能永远无用，因而浪费时间其中一些指针可能永远无用，因而浪费时间592）按需混写按需混写 l什

21、么是按需混写什么是按需混写 一一个个块块刚刚读读入入内内存存时时，所所有有指指针针都都保保持持原原样样，不不混混写写。但但将将该该块块记记录录的的数数据据库库地地址址与与相相应应的的内内存存地地址址放放入入转转换表。换表。检索检索至某个指针至某个指针A时，将其混写。时，将其混写。l按需混写的特点按需混写的特点一个块中的指针需要分次混写，可能会浪费时间一个块中的指针需要分次混写，可能会浪费时间不需要的指针不必混写，因而能够节约时间不需要的指针不必混写，因而能够节约时间603）显式控制显式控制 l什么是显式控制什么是显式控制 某某些些应应用用中中，应应用用程程序序员员可可能能会会知知道道是是否否会

22、会沿沿某某个个块中的指针进行检索。因而可由程序员显式控制。块中的指针进行检索。因而可由程序员显式控制。612.4.3块块l主要内容主要内容块和记录块和记录地址地址的表示的表示普通记录地址普通记录地址索引结构索引结构F记录在块中的记录在块中的存储存储方式方式BOLB62二、记录在块中的存储方式二、记录在块中的存储方式63 (1)unspanned(2)spanned(3)mixedrecordtypesclustering(4)splitrecordsOptions for storing records in blocks:64 lrecordsmustbewithinoneblockbloc

23、k1block2.(1)unspannedR1R2R3R4R565 lSpannedblock1block2.(2)SpannedR1R2R3(a)R3(b)R6R5R4R7(a)needindicationneedindicationofpartialrecordofcontinuation“pointer”torest(+fromwhere?)66 lUnspannedismuchsimpler,butmaywastespacelSpannedessentialifrecordsizeblocksizeSpanned vs. unspanned:67 Example106recordsea

24、chofsize2,050bytes(fixed)blocksize=4096bytesblock1block22050byteswasted20462050byteswasted2046R1R2lTotalwasted=2x109Utiliz=50%lTotalspace=4x10968 lMixed-recordsofdifferenttypes(e.g.EMPLOYEE,DEPT)allowedinsameblocke.g.,ablock(3)MixedrecordtypesDEPTd1EMPe1EMPe269Whydowewanttomix?Answer:CLUSTERINGRecor

25、dsthatarefrequentlyaccessedtogethershouldbeinthesameblock70Compromise:Nomixing,butkeeprelatedrecordsinsamecylinder.71 ExampleQ1:selectA#,C_NAME,C_CITY,fromDEPOSIT,CUSTOMERwhereDEPOSIT.C_NAME=CUSTOMER.C.NAMEablockCUSTOMER,NAME=SMITHDEPOSIT,NAME=SMITHDEPOSIT,NAME=SMITH72 lIfQ1frequent,clusteringgoodlB

26、utifQ2frequentQ2:SELECT*FROMCUSTOMERCLUSTERINGISCOUNTERPRODUCTIVE73FixedpartinoneblockTypicallyforhybridformatVariablepartinanotherblock(4)Splitrecords742.4.3块块l主要内容主要内容块和记录块和记录地址地址的表示的表示普通记录地址普通记录地址索引结构索引结构记录在块中的记录在块中的存储方式存储方式FBOLB75三、三、BLOBlBLOB的存储的存储lBLOB的检索的检索76BLOB的存储的存储l存储在一系列块中。即跨块存储。存储在一系列块中

27、。即跨块存储。将将BLOB存储在磁盘的一个或多个柱面上的连续块中存储在磁盘的一个或多个柱面上的连续块中将将BLOB存储在块的链表中存储在块的链表中将将BLOB进行分割，存储在几个磁盘中进行分割，存储在几个磁盘中77BLOB的检索的检索l只检索记录的非只检索记录的非BLOB字段字段l一一次次一一个个地地请请求求BLOB块块，而而与与记记录录的的其其余余部部分分无关。无关。(eg.观看电影观看电影)l请求请求BLOB内的部分，而不必接收整个内的部分，而不必接收整个BLOB。这需要合适的索引结构。这需要合适的索引结构。(eg.观看或收听视频观看或收听视频或音频的某个指定片段或音频的某个指定片段)78

28、2.4数据组织方式数据组织方式l2.4.1数据组织方法概述数据组织方法概述l2.4.2记录记录l2.4.3块块l2.4.4增删改记录增删改记录792.4.4增删改记录增删改记录l1 1插入记录插入记录l2 2删除记录删除记录l3 3更新记录更新记录801插入记录插入记录l记录无序记录无序找到有空闲空间的块找到有空闲空间的块没有，则找一个新块没有，则找一个新块81l记录顺序存储记录顺序存储需要移动记录需要移动记录能在当前块中为插入记录找到空间能在当前块中为插入记录找到空间l在块中移动记录在块中移动记录l调整偏移量表中的表项调整偏移量表中的表项l插入新记录，并填偏移量表插入新记录，并填偏移量表在在

29、“邻近块邻近块”中找空间中找空间l将当前块的最高记录移到邻近块中，并移动两个块的中记录将当前块的最高记录移到邻近块中，并移动两个块的中记录l当当有有外外部部指指针针指指向向某某个个跨跨块块移移动动的的记记录录时时，需需要要在在原原位位置置留留下一个下一个“转发地址转发地址”创建一个溢出块创建一个溢出块822删除记录删除记录l回收空间的方法回收空间的方法移动记录，使块中间总有一个未用空间移动记录，使块中间总有一个未用空间在块首部维护一个可用空间列表在块首部维护一个可用空间列表去除溢出块去除溢出块l悬挂指针问题悬挂指针问题83DanglingpointersConcern with deletio

30、nsR1?84 PhysicalIds(对于偏移量表方式）对于偏移量表方式） A blockThis spaceThis space cannever re-used be re-usedLeave“MARK”inmaporoldlocation85 LogicalIds（对于映射表方式）对于映射表方式）Leave“MARK”inmaporoldlocationNever reuseID 7788 nor space in map.IDLOC7788map863更新记录更新记录l更新定长记录更新定长记录对存储系统无影响对存储系统无影响87l更新变长记录更新变长记录新记录比旧记录长新记录比旧记录

31、长l移动记录移动记录l创建溢出块创建溢出块新记录比旧记录短新记录比旧记录短l合并空闲空间合并空闲空间l去除溢出块去除溢出块88第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE和和TeraData的数据库结构和体系结构的数据库结构和体系结构892.5索引组织方式索引组织方式l索引的好外索引的好外索引块数量通常比数据块数量少得多索引块数量通常比数据块数量少得多可可以以有有有有效效的的方方法法查查找找索索引引（普普通通索索引引：二二分分查查找找

32、；树形索引：从根到叶；树形索引：从根到叶；HASH索引：直接计算）索引：直接计算）索引文件可能足够小，可以永久地存放在内存缓冲区索引文件可能足够小，可以永久地存放在内存缓冲区中，从而减少中，从而减少I/O操作操作90l几几类索引方法类索引方法排序文件上的简单索引排序文件上的简单索引非排序文件上的辅助索引非排序文件上的辅助索引B树及其变种树及其变种HASH多多属性索引属性索引912.5索引组织方式索引组织方式l2.5.1顺序文件上的索引顺序文件上的索引l2.5.2辅助索引辅助索引l2.5.3B树及其变种树及其变种l2.5.4HASH文件文件l2.5.5多属性索引多属性索引922.5.1顺序文件上

33、的索引顺序文件上的索引l主要内容主要内容稠密索引稠密索引稀疏索引稀疏索引多级索引多级索引取重复值属性上的索引取重复值属性上的索引索引维护索引维护931.稠密索引稠密索引l什么是稠密索引什么是稠密索引索引块中存放索引块中存放每条记录每条记录的码以及指向记录本身的指针的码以及指向记录本身的指针94 Sequential File201040306050807010090l示例示例95 Sequential File201040306050807010090Dense Index102030405060708090100110120l示例示例96l稠密索引的查找方法稠密索引的查找方法二分查找二分查找

34、972.稀疏索引稀疏索引l什么是稀疏索引什么是稀疏索引索索引引块块中中存存放放每每个个数数据据块块中中第第一一条条记记录录的的码码值值及及指指向向该记录的指针。该记录的指针。稀疏：每个存储块只有一个索引项。稀疏：每个存储块只有一个索引项。98 Sequential File201040306050807010090l示例示例99 Sequential File201040306050807010090Sparse Index1030507090110130150170190210230l示例示例100l稀疏索引的查找方法稀疏索引的查找方法（查找码为（查找码为K K的记录）的记录）首先用二分首先

35、用二分查查找法找法查查找找码值码值小于或等于小于或等于K K的最大的最大码值码值然后根据它的指然后根据它的指针针找到相找到相应应的数据的数据块块在该数据块中搜索，查找码值为在该数据块中搜索，查找码值为K K的记录的记录 1013.多级索引多级索引l多级索引的引入多级索引的引入索索引引较较小小时时，可可以以将将其其存存放放到到内内存存或或磁磁盘盘的的预预留留存存储储区区中中，从从而而使使索索引引查查找找速速度度较较快快。当当索索引引较较大大时时，可可以以在在索索引引上上再再建建一一级级索索引引，并并将将新新的的索索引引本本身身存存放放到到某个固定的地方，这就是多级索引。某个固定的地方，这就是多级

36、索引。通过在索引上再建索引，能够使第一级索引更为有效。通过在索引上再建索引，能够使第一级索引更为有效。二级索引或更高级的索引必须是稀疏索引。二级索引或更高级的索引必须是稀疏索引。102 Sequential File201040306050807010090l示例示例103 Sequential File201040306050807010090Sparse Index1030507090110130150170190210230l示例示例104 Sequential File201040306050807010090Sparse 2nd level1030507090110130150170

37、1902102301090170250330410490570l示例示例105l多级索引的查找方法多级索引的查找方法（查找码为（查找码为K K的记录，以两级索引为例）的记录，以两级索引为例） 首首先先用用二二分分查查找找法法查查找找二二级级索索引引，找找到到码码值值小小于于或或等等于于K K的最大的最大码值码值根根据据该该最最大大码码值值对对应应的的指指针针找找到到一一级级索索引引的的相相应应存存储储块块B B若存若存储块储块B B不在内存，将其不在内存，将其读读入内存入内存利用一利用一级级索引索引查查找找码值为码值为K K的的记录记录l如果一如果一级级索引是稠密索引：同稠密索引索引是稠密索引

38、：同稠密索引查查找方法找方法l如果一级索引是稀疏索引：同稀疏索引查找方法如果一级索引是稀疏索引：同稀疏索引查找方法 1064.取重复值属性上的索引取重复值属性上的索引l四种策略四种策略稠密索引：两种策略稠密索引：两种策略稀疏索引：两种策略稀疏索引：两种策略107方法一方法一l稠密索引。每一个具有码值稠密索引。每一个具有码值K的记录设一索引项。的记录设一索引项。允许索引文件中出现重复的查找码允许索引文件中出现重复的查找码l示例示例108Duplicatekeys10102010302030304540109 10102010302030304540101010202030303010102010

39、3020303045401010102020303030Denseindex,onewaytoimplement?Duplicatekeys110l查找查找找找出出具具有有码码值值K K的的第第一一个个索索引引项项，后后面面紧紧接接着着的的为为其其他的具有他的具有码值码值K K的索引的索引项项。依据依据这这些索引指些索引指针针可以找到所有具有可以找到所有具有码值码值K K的的记录记录l缺点缺点索引大，可能不能放入内存，从而增加索引大，可能不能放入内存，从而增加I/OI/O111方法二方法二l稠密索引。为所有码值为稠密索引。为所有码值为K的记录只设一个索引的记录只设一个索引项。该索引项的指针指向

40、码值为项。该索引项的指针指向码值为K的第一个记录。的第一个记录。l示例示例112 1010201030203030454010203040Denseindex,betterway?Duplicatekeys113l查找查找首先利用索引找到首先利用索引找到码值为码值为K K的第一个的第一个记录记录然然后后在在数数据据文文件件中中顺顺序序向向下下查查找找其其他他码码值值为为K的的记记录录（必然相邻）（必然相邻） 114方法三方法三l稀疏索引。索引的码稀疏索引。索引的码-指针对对应数据文件中每指针对对应数据文件中每个块的第一个查找码。个块的第一个查找码。l示例示例115 10102010302030

41、30454010102030Sparseindex,oneway?Duplicatekeyscareful if lookingfor 20 or 30!116l查找查找首首先先找找到到索索引引中中键键值值小小于于或或等等于于K K的的最最后后一一个个索索引引项项E1E1然然后后向向索索引引起起始始方方向向搜搜索索，直直到到第第一一个个索索引引项项或或找找到到一个一个严严格小于格小于K K的索引的索引项项E2E2为为止止从从E2到到E1的的索索引引项项（含含E2和和E1）指指向向所所有有可可能能包包含含码码为为K的的记记录录的的数数据据块块。在在这这些些数数据据块块中中顺顺序序查查找找码码为为

42、K的记录即可的记录即可 117方法四方法四l稀疏索引。为每个数据块中新的（未在前一存储稀疏索引。为每个数据块中新的（未在前一存储块中出现过的）最小查找码设一索引项。要是在块中出现过的）最小查找码设一索引项。要是在存储块中没有新码值出现，那么就为该块中唯一存储块中没有新码值出现，那么就为该块中唯一的码值设一索引项。的码值设一索引项。l示例示例118 1010201030203030454010203030Sparseindex,anotherway?Duplicatekeys place first new key from block119 l查找查找在索引中在索引中查查找第一个找第一个码值满

43、码值满足如下条件之一的索引足如下条件之一的索引项项l等于等于K Kl小于小于K K，但下一个但下一个码值码值大于大于K K按按照照这这个个索索引引项项的的指指针针找找到到相相应应的的数数据据块块，在在该该数数据据块块中中查查找到找到码值为码值为K K的所有的所有记录记录。l如如果果其其中中一一个个记记录录为为该该块块的的第第一一条条记记录录，则则继继续续向向上上查查找找其其他他数数据据块块，直直到到找找出出所所有有查查找找码码为为K K的的记录记录。l如如果果其其中中一一个个记记录录为为该该块块的的最最后后一一条条记记录录，则则继继续续向向下下查查找找其其他他数数据据块块，直直到到找找出出所所

44、有有查查找找码码为为K的记录。的记录。 120 1010201030204030454010203030example401215.索引维护索引维护l删除删除从稠密索引中从稠密索引中删删除某个除某个记录记录从稀疏索引中删除某个记录从稀疏索引中删除某个记录 l插入插入向稀疏索引中插入某个记录向稀疏索引中插入某个记录向稠密索引中向稠密索引中插入插入某个记录某个记录122 Deletionfromdenseindex20104030605080701020304050607080123 Deletionfromdenseindex20104030605080701020304050607080 de

45、lete record 304040124 Deletionfromsparseindex20104030605080701030507090110130150125 Deletionfromsparseindex20104030605080701030507090110130150 delete record 40126 Deletionfromsparseindex20104030605080701030507090110130150 delete record 304040127 Deletionfromsparseindex2010403060508070103050709011013

46、0150 delete records 30 & 405070128 Insertion,sparseindexcase20103050406010304060129 Insertion,sparseindexcase20103050406010304060 insert record 3434 our lucky day! we have free space where we need it!130 Insertion,sparseindexcase20103050406010304060 insert record 1515203020Immediate reorganization13

47、1 Insertion,sparseindexcase20103050406010304060 insert record 2525overflow blocks(reorganize later.)132 Insertion,denseindexcase Similar Often more expensive . . . 133操作操作稠密索引稠密索引稀疏索引稀疏索引插入记录插入记录插入插入更新更新(？)删除记录删除记录删除删除更新更新(？)1342.5索引组织方式索引组织方式l2.5.1顺序文件上的索引顺序文件上的索引l2.5.2辅助索引辅助索引l2.5.3B树及其变种树及其变种l2.5

48、.4HASH文件文件l2.5.5多属性索引多属性索引1352.5.2辅助索引辅助索引l辅助索引的特点辅助索引的特点l辅助索引的实现技术辅助索引的实现技术1361.辅助索引的特点辅助索引的特点l辅辅助助索索引引不不决决定定数数据据文文件件中中记记录录的的存存放放位位置置，只只能指明记录的当前存放位置。能指明记录的当前存放位置。l辅辅助助索索引引总总是是稠稠密密索索引引。原原因因：辅辅助助索索引引不不影影响响记记录录的的存存储储位位置置，因因而而不不能能根根据据它它来来预预测测码码值值不不在索引中显式指明的任何记录位置。在索引中显式指明的任何记录位置。l建辅助索引的属性通常取重复值建辅助索引的属性

49、通常取重复值137 SecondaryindexesSequencefield503070204080101006090138 SecondaryindexesSequencefield503070204080101006090 Sparse index30208010090.does not make sense!139 SecondaryindexesSequencefield503070204080101006090 Dense index10203040506070.105090.sparsehighlevel140 Withsecondaryindexes:lLowestleveli

50、sdenselOtherlevelsaresparseAlso:Pointersarerecordpointers(notblockpointers;notcomputed)1412. 2. 辅助索引的辅助索引的实现技术实现技术142 Duplicatevalues&secondaryindexes10204020401040104030143 Duplicatevalues&secondaryindexes1020402040104010403010101020203040404040.one option.Problem:excess overhead! disk space search

51、 time144 Duplicatevalues&secondaryindexes1020402040104010403010another option.403020Problem:variable sizerecords inindex!145 Duplicatevalues&secondaryindexes10204020401040104030102030405060.Anotheridea:Chainrecordswithsamekey?Problems:NeedtoaddfieldstorecordsNeedtofollowchaintoknowrecords146 Duplica

52、tevalues&secondaryindexes10204020401040104030102030405060.buckets147 Why“bucket”ideaisusefulIndexesRecordsName:primary EMP(name,dept,floor,.)Dept:secondaryFloor:secondary148 Query:Getemployeesin(ToyDept)(2ndfloor)Dept. indexEMP Floor indexToy 2ndIntersecttoybucketand2ndFloorbuckettogetsetofmatchingE

53、MPs149 ThisideausedintextinformationretrievalDocuments.the cat is fat .was raining cats and dogs.Fido the dog .Inverted listscatdog150151152祝祝大大家家国国庆庆节节快快乐乐！1532.5索引组织方式索引组织方式l2.5.1顺序文件上的索引顺序文件上的索引l2.5.2辅助索引辅助索引l2.5.3B树及其变种树及其变种l2.5.4HASH文件文件l2.5.5多属性索引多属性索引1542.5.3B树及其变种树及其变种lB树的引入树的引入 B树是为解决大型索引的组

54、织和维护而产生的一种数树是为解决大型索引的组织和维护而产生的一种数据结构。据结构。 155 ConventionalindexesAdvantage:-Simple-IndexissequentialfilegoodforscansDisadvantage:-Insertsexpensive,and/or-Losesequentiality&balance156 ExampleIndex(sequential)continuousfreespace1020304050607080903931353632383433overflow area(not sequential)157 lNEXT:A

55、nothertypeofindexGiveuponsequentialityofindexTrytoget“balance”158lB树的特点树的特点高效高效易变易变平衡平衡对硬件相对独立对硬件相对独立B树是索引组织的一种标准形式树是索引组织的一种标准形式159l本节主要内容本节主要内容基本基本B树树B+B+树树B B树的其它变种树的其它变种二分二分B B树树B树的并发控制树的并发控制1601.基本基本B树树l一棵秩一棵秩(order)为为n的的B树具有下列特征：树具有下列特征：1.每个结点最多包含每个结点最多包含n个个key。2.除除了了根根结结点点外外，每每个个结结点点最最少少包包含含n/

56、2个个key（根根结结点点最最少含有一项）。少含有一项）。3.含含有有j项项的的结结点点，有有j+1个个儿儿子子（叶叶结结点点除除外外，它它没没有有儿儿子子)。4.所有的叶结点都在同一级上。所有的叶结点都在同一级上。161l一个含有一个含有j项的结点的结构项的结点的结构Ki(1ij)是码，并且是码，并且kiki+1，Pi是指引元，是指引元，Pi所指向的子树中码值均小于所指向的子树中码值均小于Ki+1大于等于大于等于Ki。 在实现时一般在结点中附加一项信息指出结点当前所含在实现时一般在结点中附加一项信息指出结点当前所含有的实际项数有的实际项数j。1622.B+树树l什么是什么是B+树树B树树+顺

57、序集顺序集163 RootB+Tree Examplen=31001201501803035113035100101110120130150156179180200164 Samplenon-leaftokeystokeystokeystokeys5757 k8181 k95 95578195165 Sampleleafnode:Fromnon-leafnodetonextleafinsequence578195Torecordwithkey57Torecordwithkey81Torecordwithkey85166 Sizeofnodes:n+1pointersnkeys(fixed)16

58、7 DontwantnodestobetooemptylUseatleastNon-leaf: (n+1)/2 pointersLeaf: (n+1)/2 pointerstodata168 Fullnodemin.nodeNon-leafLeafn=31201501803035113035countsevenifnull169 B+treerulestreeofordern(1)Allleavesatsamelowestlevel(balancedtree)(2)Pointersinleavespointtorecordsexceptfor“sequencepointer”170 Numbe

59、rofpointers/keysforB+treeNon-leaf(non-root)n+1n(n+1)/2 (n+1)/2- 1Leaf(non-root)n+1nRootn+1n11Max Max Min Min ptrs keys ptrsdata keys(n+1)/2 (n+1)/2171lB+树的查找树的查找随机查找随机查找l从根到叶的一条通路从根到叶的一条通路。（查找通路）。（查找通路）顺序查找顺序查找l随随机机查查找找通通路路的的末末端端结结点点为为顺顺序序查查找找提提供供了了入入口口点点，从从这这个个入入口口点点开开始始沿沿着着顺顺序序集集就就可可以以进进行行顺顺序查找。序查

60、找。l若是从头开始顺序查找，可以从顺序集的链头若是从头开始顺序查找，可以从顺序集的链头SH开始。开始。172lB+树的维护树的维护插入插入删除删除173InsertintoB+tree(a)simplecasespaceavailableinleaf(b)leafoverflow(c)non-leafoverflow(d)newroot174(a)spaceavailableinleaf-Insertkey=32n=3351130313010032175(b)leafoverflow-Insertkey=7n=335113031301003577176(c)non-leafoverflow-I

61、nsertkey=160n=3100120150180150156179180200160180160179177(d)Newroot-insert45n=31020301231012202530324040454030newroot178(a)Simplecase(b)Coalescewithneighbor(sibling)(c)Re-distributekeys(d)Cases(b)or(c)atnon-leafDeletionfromB+tree179(a)SimplecaseDelete3010401001020304050n=4180(b)CoalescewithsiblingDe

62、lete5010401001020304050n=440181(c)RedistributekeysDelete501040100102030354050n=43535182404530372526202210141310203040(d)Non-leafcoaleseDelete37n=440302525newroot183删除操作注意删除操作注意lB+索引非叶结点中的码仅仅起到了分隔两棵子索引非叶结点中的码仅仅起到了分隔两棵子树的作用树的作用，因而又称为分隔元。，因而又称为分隔元。对于对于Ki来说它可以取来说它可以取Pi-1所指向的子树中最大码和所指向的子树中最大码和Pi所所指向子树中最小

63、码（包括该最小码）之间的任何值，指向子树中最小码（包括该最小码）之间的任何值，而不必是数据记录中实际存在的码值而不必是数据记录中实际存在的码值184删除操作注意（删除操作注意（Cont.)l因此因此B+树的删除总是发生在数据块上，比树的删除总是发生在数据块上，比B树的删除情树的删除情况单一。况单一。l只要删除后数据块中的记录数仍有一半以上就不必修改只要删除后数据块中的记录数仍有一半以上就不必修改索引项，即使索引项中的码值已实际删去。索引项，即使索引项中的码值已实际删去。l只有当删除后数据块中的记录数不足一半而要只有当删除后数据块中的记录数不足一半而要“重新分重新分配配”或或“合并合并”时可能要

64、调整索引项或者删除索引项。时可能要调整索引项或者删除索引项。1853.B树的其它变种树的其它变种l降低降低B树的高度是提高树的高度是提高B树效率的关键。树效率的关键。l降低降低B树高度两种方法树高度两种方法提高空间利用率提高空间利用率尽可能提高秩尽可能提高秩由此又衍生出不少由此又衍生出不少B树的变种。树的变种。1861)提高空间利用率提高空间利用率B*树树lB树树和和B+树树的的每每个个结结点点都都规规定定至至少少装装满满一一半半，存贮空间的利用率为存贮空间的利用率为0.5-1.0，平均利用率为，平均利用率为0.75。l若若让让结结点点至至少少装装满满2/3以以上上，则则最最低低空空间间利利用

65、用率率就就由由0.5提提高高到到0.66。这这样样B树树的的高高度度得得以以降降低低。这种改进后的这种改进后的B树称为树称为B*树。树。l它的查找算法和它的查找算法和B树相同，只有插入和删除算法树相同，只有插入和删除算法中的中的“分裂分裂”和和“合并合并”稍有改变。稍有改变。1872)增大增大n值值前缀前缀B树和压缩技术树和压缩技术l前缀前缀B树树l压缩技术压缩技术188前缀前缀B树树lB+树树中中索索引引部部分分的的码码值值仅仅仅仅起起分分隔隔左左右右子子树树的的作用，因而它不必由实际的码组成。作用，因而它不必由实际的码组成。l为了使一个块中能存放更多的索引项提高为了使一个块中能存放更多的索

66、引项提高B+树树的秩以降低的秩以降低B+树的高度，可以选择码的最短一树的高度，可以选择码的最短一个前缀作为分隔符，这就是个前缀作为分隔符，这就是前缀前缀B树树。189 190l前缀前缀B树的问题树的问题选择码的最短一个前缀作为分隔符有时并不有效。选择码的最短一个前缀作为分隔符有时并不有效。191l解决方法解决方法方法方法1：采用一个算法，扫视邻近的码，取一对具有：采用一个算法，扫视邻近的码，取一对具有较短前缀的码作为分隔值。较短前缀的码作为分隔值。 例：在上例中可以选择例：在上例中可以选择“prepare”和和“programmer”这对码，用这对码，用“pro”作为它们的分隔作为它们的分隔值

67、。值。 这样会造成顺序集诸结点中所包含的项不太均衡，有这样会造成顺序集诸结点中所包含的项不太均衡，有的结点含有较多的项而有的结点中项较少，但一般并的结点含有较多的项而有的结点中项较少，但一般并不影响总的操作效率。不影响总的操作效率。192193l解决方法解决方法方法方法2：采用压缩技术：采用压缩技术 194压缩技术压缩技术l前缀压缩前缀压缩把码和其紧前一个码首部相同的位数用一个计数器把码和其紧前一个码首部相同的位数用一个计数器记下而去掉相同部分，这叫做记下而去掉相同部分，这叫做前缀前缀(prefix)压缩压缩。l后缀压缩后缀压缩由于索引项中的码值可以取大于左子树中最大码值由于索引项中的码值可以

68、取大于左子树中最大码值而小于（或等于）右子树中最小码值中的任何一个而小于（或等于）右子树中最小码值中的任何一个值，利用这个特点可以对码的尾部进行压缩，称为值，利用这个特点可以对码的尾部进行压缩，称为后缀后缀(suffix)压缩压缩。195 196压缩技术压缩技术l指指针针可可以以采采用用基基地地址址加加位位移移代代替替绝绝对对地地址址的的方方法法进行压缩。进行压缩。基地址只存贮一次，指针用位移值来表示。基地址只存贮一次，指针用位移值来表示。位移值比绝对地址小得多，因而节省了存贮空间。位移值比绝对地址小得多，因而节省了存贮空间。l压缩技术可以提高结点的秩，但是要耗费一定的压缩技术可以提高结点的秩

69、，但是要耗费一定的CPU时间来处理码和指引元的压缩和恢复。时间来处理码和指引元的压缩和恢复。1974二分二分B树树lB树树是是作作为为文文件件的的索索引引组组织织而而引引入入的的，但但是是它它动动态态平平衡衡的的突突出出优优点点使使人人们们也也想想在在内内存存中中使使用用它它。由由于于内内存存容容量量小，所以通常是使用小，所以通常是使用“二分二分B树树”，也称为，也称为2-3树。树。l二分二分B树是秩为树是秩为2的的B树，每个结点有树，每个结点有1-2个码，个码，2-3个指针个指针l在二分在二分B树中，为了节省内存不让树中，为了节省内存不让B树中的结点空一半，树中的结点空一半，因而用链结构的方

70、法来表示一个结点。因而用链结构的方法来表示一个结点。198 199二分二分B树树l二二分分B树树中中右右指指引引元元可可以以指指向向一一个个兄兄弟弟结结点点（对对应应B树树中中同同一一结结点点的的右右项项），也也可可以以指指向向它它的的儿儿子结点。用一个二进制位的子结点。用一个二进制位的0，1加以区分。加以区分。l删除和插入算法要增加许多细节来正确而无遗漏删除和插入算法要增加许多细节来正确而无遗漏的修改指针，不仅要修改上一级结点中的，而且的修改指针，不仅要修改上一级结点中的，而且要修改更高一级中的指针。要修改更高一级中的指针。2005.B树的并发控制树的并发控制l例例1：甲甲进进程程要要查查找

71、找以以6为为码码的的记记录录；乙乙进进程程正正把把记录记录4插入结点插入结点B。甲甲进进程程正正在在读读结结点点A，从从结结点点A它它知知道道此此记记录录应应在在结结点点B中。中。与与此此同同时时，乙乙进进程程正正把把记记录录4插插入入结结点点B，引引起起了了B的的分裂。分裂。因此当甲进程到达结点因此当甲进程到达结点B时就找不到以时就找不到以6为码的记录为码的记录了。了。201 甲进程正在读结甲进程正在读结点点A，从结点从结点A它它知道此记录应在知道此记录应在结点结点B中。中。甲进程要查找以甲进程要查找以6为码的记录；乙进程为码的记录；乙进程正把记录正把记录4插入结点插入结点B。与此同时，乙与

72、此同时，乙进程正把记录进程正把记录4插入结点插入结点B，引引起了起了B的分裂。的分裂。202 甲进程正在读结甲进程正在读结点点A，从结点从结点A它它知道此记录应在知道此记录应在结点结点B中。中。甲进程要查找以甲进程要查找以6为码的记录；乙进程为码的记录；乙进程正把记录正把记录4插入结点插入结点B。与此同时，乙与此同时，乙进程正把记录进程正把记录4插入结点插入结点B，引引起了起了B的分裂。的分裂。因此当甲进程因此当甲进程到达结点到达结点B时就时就找不到以找不到以6为码为码的记录了。的记录了。读写冲突203l例例2：甲进程插入：甲进程插入2,乙进程删除乙进程删除8甲甲进进程程正正在在把把2插插入入

73、结结点点C，它它记记下下的的查查找找通通路路是是ABC。乙乙进进程程正正到到达达结结点点E准准备备把把8删删去去。它它形形成成的的查查找找通通路路是是ABE。甲进程插入完毕后乙进程的返回道路就被破坏了。甲进程插入完毕后乙进程的返回道路就被破坏了。204 甲进程插入甲进程插入2,乙进程删除乙进程删除8甲进程正在把甲进程正在把2插入结点插入结点C，它它记下的查找通路是记下的查找通路是ABC。乙进程正到达结点乙进程正到达结点E准备把准备把8删删去。它形成的查找通路是去。它形成的查找通路是ABE。205 甲进程插入甲进程插入2,乙进程删除乙进程删除8甲进程正在把甲进程正在把2插入结点插入结点C，它它记

74、下的查找通路是记下的查找通路是ABC。乙进程正到达结点乙进程正到达结点E准备把准备把8删删去。它形成的查找通路是去。它形成的查找通路是ABE。甲进程插入完毕后乙进程的返甲进程插入完毕后乙进程的返回道路就被破坏了。回道路就被破坏了。写写冲突206l控制并发办法控制并发办法加加“锁锁”但是对于但是对于B树来说，树来说，仅仅锁住正在处置的那个结点显仅仅锁住正在处置的那个结点显然是不够了。然是不够了。207l读操作的封锁方法读操作的封锁方法 一个一个查查找找进进程可能被干程可能被干扰扰的原因的原因l当当我我们们刚刚刚刚找找出出了了将将被被查查找找的的子子树树时时，这这棵棵子子树树或或者者由由于于“分分

75、裂裂”使使我我们们只只能能到到达达它它的的一一个个真真子子集集；或者由于合并而消失。或者由于合并而消失。读操作的封锁方法读操作的封锁方法l使使用用某某结结点点就就立立刻刻把把它它锁锁住住（加加读读锁锁），等等此此进进程程到到达达下下一一层层结结点点（或或进进程程终终止止）时时再再将将它它释释放放。这棵树的其余部分可以被别的进程使用。这棵树的其余部分可以被别的进程使用。 208l更新操作的封锁方法更新操作的封锁方法 简单方法简单方法l对对于于更更新新，由由于于它它可可能能会会沿沿开开始始查查找找时时形形成成的的通通路路自自底底向向上上退退回回，因因此此凡凡是是查查找找过过程程中中用用过过的的结结

76、点点都都加加读读锁锁。当当它它到到达达末末端端结结点点时时就就把把这这些些结结点点的封锁升级为写锁。的封锁升级为写锁。l也也就就是是说说，整整个个查查找找通通路路都都被被它它封封锁锁，然然后后进进行行更更新新。直直到到更更新新结结束束时时，这这条条通通路路的的封封锁锁才才被被撤撤销。销。209 改进方法改进方法l在在插插入入或或删删除除时时，大大部部分分更更新新过过程程只只影影响响靠靠近近叶叶结结点点的的几几级级，一一直直影影响响到到根根的的概概率率是是很很小小的的。所所以以把把包包括括根根在在内内的的整整个个通通路路都都加加锁锁显显然然是是太太保保守守的办法。的办法。l对对于于插插入入，只只

77、要要查查找找通通路路上上存存在在项项数数小小于于n的的结结点点对对于于删删除除只只要要查查找找通通路路上上存存在在项项数数大大于于n/2的的结结点点，递归过程就不会继续下去。递归过程就不会继续下去。l改进方法改进方法在在插插入入（或或删删除除）过过程程的的第第一一步步即即查查找找过过程程中中遇遇到到所所含含项项数数小小于于n（或或大大于于n/2）的的结结点点时时，就就可可以以释释放放前前面面加加读读锁锁的的结结点点，以以减减少少更更新新进进程封锁的结点。程封锁的结点。2102.5索引组织方式索引组织方式l2.5.1顺序文件上的索引顺序文件上的索引l2.5.2辅助索引辅助索引l2.5.3B树及其

78、变种树及其变种l2.5.4HASH文件文件l2.5.5多属性索引多属性索引2112.5.4Hash索引l基本基本Hashl可扩充可扩充Hashl线性线性HashlHash索引与索引与B+树索引比较树索引比较212一、基本一、基本Hashl1.Hash的基本结构的基本结构l2.Hash表的增删操作表的增删操作l3.Hash表索引的效率表索引的效率213一、基本一、基本Hashl1.Hash的基本结构的基本结构l2.Hash表的增删操作表的增删操作l3.Hash表索引的效率表索引的效率214keyh(key)Hashing.Buckets(typically 1disk block)215.Two

79、alternativesrecords.(1) key h(key)216(2) key h(key)Indexrecordkey 1Twoalternatives217Examplehashfunction（1）lKey=x1x2xnnbytecharacterstringlHavebbucketslh:addx1+x2+.xncomputesummodulob218Examplehashfunction（2）l把关键字的值化为二进制序列。把关键字的值化为二进制序列。l把此二进制序列划分成定长的若干组，若最后一把此二进制序列划分成定长的若干组，若最后一组数目不足则补组数目不足则补0 0。l把

80、若干组二进制迭加起来，得一整数。把若干组二进制迭加起来，得一整数。l以存贮区桶的个数除此整数，取其余数作为如上以存贮区桶的个数除此整数，取其余数作为如上关键字对应的桶号。关键字对应的桶号。219Examplehashfunction（2）例：例：l关键字的值化为二进制序列：关键字的值化为二进制序列： 0101000100111 0101000100111l分组，补分组，补0 0： 0101 0101 0001 0001 0011 0011 1 1000000l相加：相加：5+1+3+8=175+1+3+8=17l设桶个数为设桶个数为6 6，则桶号为：，则桶号为：5 5220Goodhashfu

81、nction:Expectednumberofkeys/bucketisthesameforallbuckets221Withinabucket:lDowekeepkeyssorted?lYes,ifCPUtimecritical&Inserts/Deletesnottoofrequent222一、基本一、基本Hashl1.Hash的基本结构的基本结构l2.Hash表的增删操作表的增删操作l3.Hash表索引的效率表索引的效率2232.Hash表的增删操作表的增删操作l插入操作插入操作l删除操作删除操作2242.Hash表的增删操作表的增删操作l插入操作插入操作l删除操作删除操作225EXAM

82、PLE：2records/bucketINSERT:h(a)=1h(b)=2h(c)=1h(d)=00123dacbh(e)=1e2262.Hash表的增删操作表的增删操作l插入操作插入操作l删除操作删除操作227删除操作删除操作l直接删除直接删除l置删除标记置删除标记2280123abcedEXAMPLE:deletionDelete:effgmaybe move“g” upcd229一、基本一、基本Hashl1.Hash的基本结构的基本结构l2.Hash表的增删操作表的增删操作l3.Hash表索引的效率表索引的效率230空间利用率空间利用率lTrytokeepspaceutilizatio

83、nbetween50%and80%Utilization=#keysusedtotal#keysthatfitlIf80%,overflowssignificantdependsonhowgoodhashfunctionis&on#keys/bucket231Howdowecopewithgrowth?lOverflowsandreorganizationslDynamichashinglExtensiblelLinear232二、可扩充二、可扩充hashl1.可扩充可扩充hash的基本结构的基本结构l2.可扩充可扩充hash的插入操作的插入操作l3.可扩充可扩充hash的删除操作的删除操作2

84、33二、可扩充二、可扩充hashl1.可扩充可扩充hash的基本结构的基本结构l2.可扩充可扩充hash的插入操作的插入操作l3.可扩充可扩充hash的删除操作的删除操作234Extensiblehashing:twoideas(a)Useiofbbitsoutputbyhashfunctionbh(K)useigrowsovertime.00110101235(b)Usedirectoryh(K)i tobucket.236二、可扩充二、可扩充hashl1.可扩充可扩充hash的基本结构的基本结构l2.可扩充可扩充hash的插入操作的插入操作l3.可扩充可扩充hash的删除操作的删除操作23

85、72.可扩充可扩充hash的插入操作的插入操作l直接插入直接插入l页分裂页分裂局部深度加局部深度加1l目录分裂目录分裂放大目录，深度加放大目录，深度加1238Example:h(k)is4bits;2keys/bucketi=111000110011100Insert1010111001010New directory200011011i=222391000121001101021100Insert:01110000000110112i =Example continued0111000001110001221000121001101021100Insert:01110000000110112

86、i =Example continued011100000111000122240000110112i =2100110102110020111200000001Insert:1001Example continued1001100110100000010100111001011101113i =33241二、可扩充二、可扩充hashl1.可扩充可扩充hash的基本结构的基本结构l2.可扩充可扩充hash的插入操作的插入操作l3.可扩充可扩充hash的删除操作的删除操作242Extensiblehashing:deletionlNomergingofblockslMergeblocksandc

87、utdirectoryifpossible(Reverseinsertprocedure)243Deletionexample:lRunthruinsertexampleinreverse!244ExtensiblehashingCanhandlegrowingfiles-withlesswastedspace-withnofullreorganizationsSummary+Indirection(Notbadifdirectoryinmemory)Directorydoublesinsize-245三、线性三、线性hashl1.线性线性hash的基本结构的基本结构l2.线性线性hash的插

88、入操作的插入操作246三、线性三、线性hashl1.线性线性hash的基本结构的基本结构l2.线性线性hash的插入操作的插入操作247LinearhashinglAnotherdynamichashingschemeTwoideas:(a)Useiloworderbitsofhash01110101growsbi(b)Filegrowslinearly248Exampleb=4bits, i =2,2keys/bucket00011011010100001010m = 01 (max used block)Futuregrowthbuckets249三、线性三、线性hashl1.线性线性ha

89、sh的基本结构的基本结构l2.线性线性hash的插入操作的插入操作2502.线性线性hash的插入操作的插入操作l直接插入直接插入l增加溢出块增加溢出块l增加新桶，分裂旧桶（提升增加新桶，分裂旧桶（提升m值）值）l提升当前被使用的散列函数的位数提升当前被使用的散列函数的位数i2512.线性线性hash的插入操作的插入操作l直接插入直接插入l增加溢出块增加溢出块l增加新桶，分裂旧桶（提升增加新桶，分裂旧桶（提升m值）值）l提升当前被使用的散列函数的位数提升当前被使用的散列函数的位数i252Exampleb=4bits, i =2,2keys/bucket000110110101111100001

90、010m = 01 (max used block)FuturegrowthbucketsIfh(k)i m,thenlookatbucketh(k)ielse,lookatbucketh(k)i -2i -1Rule insert 11112532.线性线性hash的插入操作的插入操作l直接插入直接插入l增加溢出块增加溢出块l增加新桶，分裂旧桶（提升增加新桶，分裂旧桶（提升m值）值）l提升当前被使用的散列函数的位数提升当前被使用的散列函数的位数i254 Exampleb=4bits, i =2,2keys/bucket000110110101111100001010m = 01 (max u

91、sed block)Futuregrowthbuckets0101 can have overflow chains! insert 01012552.线性线性hash的插入操作的插入操作l直接插入直接插入l增加溢出块增加溢出块l增加新桶，分裂旧桶（提升增加新桶，分裂旧桶（提升m值）值）l提升当前被使用的散列函数的位数提升当前被使用的散列函数的位数i256 Exampleb=4bits, i =2,2keys/bucket000110110101111100001010m = 01 (max used block)Futuregrowthbuckets1010100101 insert 010

92、111111101012572.线性线性hash的插入操作的插入操作l直接插入直接插入l增加溢出块增加溢出块l增加新桶，分裂旧桶（提升增加新桶，分裂旧桶（提升m值）值）l提升当前被使用的散列函数的位数提升当前被使用的散列函数的位数i258 ExampleContinued:Howtogrowbeyondthis?0001101111111010010101010000m = 11 (max used block)i = 20000100 101 110 1113. . .10010010110101010101259lIfUthresholdthenincreasem(andmaybei )W

93、hendoweexpandfile?lKeeptrackof:当前散列表中的记录总数当前散列表中的记录总数当前桶数当前桶数= U260LinearHashingCanhandlegrowingfiles-withlesswastedspace-withnofullreorganizationsNoindirectionlikeextensiblehashingSummary+Canstillhaveoverflowchains-261Example:BADCASEVeryfullVeryemptyNeedtomovemhereWouldwastespace.262四、hash索引与B+树索引比

94、较263lHashinggoodforprobesgivenkeye.g.,SELECTFROMRWHERER.A=5hash索引索引与与B+树树索引比较索引比较264lINDEXING(IncludingBTrees)goodforRangeSearches:e.g.,SELECTFROMRWHERER.A5hash索引索引与与B+树树索引比较索引比较265IndexdefinitioninSQLlCreateindexnameonrel(attr)lCreateuniqueindexnameonrel(attr)definescandidatekeylDropINDEXname266CAN

95、NOTSPECIFYTYPEOFINDEX(e.g.B-tree,Hashing,)ORPARAMETERS(e.g.LoadFactor,SizeofHash,.).atleastinSQL.Note267ATTRIBUTELISTMULTIKEYINDEXe.g.,CREATEINDEXfooONR(A,B,C)Note2682.5索引组织方式索引组织方式l2.5.1顺序文件上的索引顺序文件上的索引l2.5.2辅助索引辅助索引l2.5.3B树及其变种树及其变种l2.5.4HASH文件文件l2.5.5多属性索引多属性索引2692.5.5 多属性索引270Motivation:Findreco

96、rdswhereDEPT=“Toy”ANDSAL50kMulti-key Index271StrategyI:lUseoneindex,sayDept.lGetallDept=“Toy”recordsandchecktheirsalaryI1272lUse2Indexes;ManipulatePointersToySal50kStrategyII:273lMultipleKeyIndexOneidea:StrategyIII:I1I2I3274 ExampleExampleRecordDeptIndexSalaryIndexName=JoeDEPT=SalesSAL=15kArtSalesToy10k15k17k21k12k15k15k19k275Forwhichqueriesisthisindexgood?FindRECsDept=“Sales”SAL=20kFindRECsDept=“Sales”SAL20kFindRECsDept=“Sales”FindRECsSAL=20k276第二章第二章RDBMS的物理组织的物理组织l2.1存储介质存储介质l2.2存储方式存储方式l2.3数据表示方法数据表示方法l2.4数据组织方式数据组织方式l2.5索引组织方式索引组织方式l2.6ORACLE和和TeraData的数据库结构和体系结构的数据库结构和体系结构277