RDBMS的物理组织.ppt

1,第二章 RDBMS的物理组织,2,第二章 RDBMS的物理组织,2.1 存储介质2.2 存储方式2.3 数据表示方法2.4 数据组织方式2.5 索引组织方式2.6 ORACLE和TeraData的数据库结构和体系结构,3,2.1 存储介质,几类存储器高速缓冲存储器（cache）主存储器(main memory)快擦写存储器(flash memory)磁盘存储器(magnetic-disk storage)光存储器(optical storage)磁带存储器(tape storage),4,5,第二章 RDBMS的物理组织,2.1 存储介质2.2 存储方式2.3 数据表示方法2.4 数据组织方式2.5 索引组织方式2.6 ORACLE和TeraData的数据库结构和体系结构,6,2.2 存储方式,以文件方式存储一个对象对应一个文件存储管理交由OS整个DB对应一个或若干个文件由RDBMS进行存储管理,7,存储方式,大型RDBMS的存储方式DB通常被划分成更小的单位，例如段(Segment或Area)，以增加灵活性整个DB对应一个或若干个文件，由DBMS进行存储管理不同RDBMS划分方法不同示例：ORACLE,8,示例：ORACLE的存储方式,表空间(逻辑设备)对应磁盘上一个或多个物理数据文件可以有多个表空间，逻辑地和物理地组织数据库中的数据存储。系统表空间、联机表空间、脱机表空间、永久表空间、临时表空间数据文件,9,段由多个区间组成。数据段、索引段、LONG段、回滚段、临时段等 区间由一组连续的数据块组成数据块ORACLE数据库的磁盘存取单元数据块的大小必须等于服务器操作系统块的大小或倍数,10,大型RDBMS的存储方式,划分数据库的好处：便于将数据库按联机存储和脱机存储来划分便于动态地、模块地分配不同类型的存储区便于数据的物理恢复便于有效地封锁便于处理数据安全,11,第二章 RDBMS的物理组织,2.1 存储介质2.2 存储方式2.3 数据表示方法2.4 数据组织方式2.5 索引组织方式2.6 ORACLE的数据库结构和体系结构,12,To represent:,Integer(short):2 bytese.g.,35 is,00000000,00100011,Real,floating pointn bits for mantissa,m for exponent.,13,Characters various coding schemes suggested,most popular is ascii,To represent:,Example:A:1000001a:11000015:0110101LF:0001010,14,Booleane.g.,TRUE FALSE,1111 1111,0000 0000,To represent:,Application specifice.g.,RED 1 GREEN 3 BLUE 2 YELLOW 4,15,Datese.g.:-Integer,#days since Jan 1,1900-8 characters,YYYYMMDD-7 characters,YYYYDDDTimee.g.-Integer,seconds since midnight-characters,HHMMSSFF,To represent:,16,String of charactersNull terminatede.g.,Length givene.g.,-Fixed length,3,To represent:,17,Bag of bits,Length,Bits,To represent:,18,Key Point,Fixed length items Variable length items-usually length given at beginning,19,Type of an item:Tells us how to interpret(plus size if fixed),Also,20,第二章 RDBMS的物理组织,2.1 存储介质2.2 存储方式2.3 数据表示方法2.4 数据组织方式2.5 索引组织方式2.6 ORACLE和TeraData的数据库结构和体系结构,21,2.4 数据组织方式,2.4.1 数据组织方法概述2.4.2 记录2.4.3 块2.4.4 增删改记录,22,2.4.1 数据组织方法概述,字段-记录-块-文件,23,2.4 数据组织方式,2.4.1 数据组织方法概述2.4.2 记录2.4.3 块2.4.4 增删改记录,24,2.4.2 记录,主要内容定长记录变长记录,25,1.定长记录,1）定长记录的构造 例：CREATE TABLE MovieStar(Name char(30)primary key,Address varchar(255),Gender char(1),Birthdate date);,26,27,某些机器对内存中数据地址的要求 有些机器可以对内存中地址为4的倍数的字节开始的数据进行更有效的读写(64位处理器时则为8的倍数)在某些机器上，整数等数据类型要求必须从4的倍数的地址处开始在某些机器上，双精度实数要求从8的倍数处开始 运行于这些机器上的DBMS，转换字段在块内的偏移量时必须小心。,28,为简化地址转换，并提高可移植性，可规定每一条记录在块内从4的倍数的字节处开始记录中所有的字段都从与记录偏移量为4的倍数的字节处开始,29,2）记录首部 记录首部信息通常包括以下内容:记录模式记录长度时间戳,30,记录模式通常是指向DBMS中存储该类记录模式的位置(数据字典)的一个指针模式信息 关系的属性属性类型属性在元组中出现的顺序属性或关系自身上的约束(主码、完整性约束等),31,记录长度时间戳指明记录最后一次被修改或被读的时间以及其他可能的信息记录模式,32,2.变长记录,1)具有变长字段的记录(3种表示策略)变长字段前加长度,33,先放定长字段，后放变长字段,34,变长字段单独存放在一个块中,35,2)具有重复字段的记录(3种表示策略)将重复字段放在一起，在记录首部用指针指向每个重复字段的第一次出现。例：对于记录：姓名，地址，出演过的影片指针,36,变长字段及重复字段单独存放在一个块中,37,折衷方案在记录的定长部分预留足够空间，存储下列信息：重复字段合理的出现次数指向可以找到这个重复字段其他出现的地方的指针其他出现的次数,38,3可变格式记录,可变格式记录的用途 不同信息源集成。通过只列出非空字段来节省空间。具有非常灵活的模式的记录。如一条记录的许多字段会重复或根本不出现 实现策略：自描述,39,40,2.4 数据组织方式,2.4.1 数据组织方法概述2.4.2 记录2.4.3 块2.4.4 增删改记录,41,2.4.3 块,主要内容块和记录地址的表示普通记录地址索引结构记录在块中的存储方式BOLB,42,2.4.3 块,主要内容块和记录地址的表示普通记录地址索引结构记录在块中的存储方式BOLB,43,一、块和记录地址的表示,普通记录的地址 索引结构（含指针）,44,1.普通记录的地址,两种方式物理地址与逻辑地址分别编址 逻辑地址与物理地址组合,45,(1)物理地址与逻辑地址分别编址,逻辑地址到物理地址的映射：映射表映射表为全程表移动记录和删除记录时不方便，必须修改映射表,46,47,(2)逻辑地址与物理地址组合,是结构化的地址模式 两种组合方式块的物理地址+被访问记录的码值 在每一个块内存储一个偏移量表,48,块的物理地址+被访问记录的码值,使用物理地址部分找到包含所查记录的块，然后检查块内记录以找到具有指定码值的记录查找效率不算好,49,在每一个块内存储一个偏移量表,记录的地址块的物理地址加上该记录在此块的偏移量表项中的偏移量可以在块内移动记录只需改变记录在偏移量表中的表项，指向这条记录的指针仍能找到它。如果偏移量表项足够大，能存储这条记录的“转向地址”，则可以允许记录移到另一块如果记录被删除，可以在偏移量表项中置删除标记,50,51,52,2.索引结构（含指针）,问题块在主存与二级存储器之间移动时，如何管理指针 数据库地址：8B左右内存地址：4B方法映射表方法指针混写方法,53,映射表方法,54,映射表方法,优点：记录不被固定在内存缺点：将数据库地址重复转换成内存地址,55,指针混写方法,基本思想 块从第二级存储器移到内存中时，将数据库地址空间转换为虚拟地址空间。因此一个指针包含：一个二进制位，指明指针目前是数据库地址还是混写的内存地址数据库或内存指针示例,56,57,混写指针的策略：根据混写指针的时机 自动混写 按需混写 显式控制,58,1）自动混写,什么是自动混写 块读入内存，即为它的所有指针和地址定位。如果地址A已存在于转换表中，则用相应的内存地址代替刚移进内存中的块中的A，并将“混写”位置1如果A不在转换表中，仍保持为数据库指针检索至指针A时，如果其为数据库指针，则查找转换表，看数据库地址A当前是否有相应的内存地址，有则代替。没有，则将相应块读入内存缓冲区，并用相应内存地址代替A（混写），同时将其放入转换表。,59,自动混写的特点 当块被装载进内存时，即试图快速、有效地混写所有指针。一次混写所有可混写的指针，可能会节省时间其中一些指针可能永远无用，因而浪费时间,60,2）按需混写,什么是按需混写 一个块刚读入内存时，所有指针都保持原样，不混写。但将该块记录的数据库地址与相应的内存地址放入转换表。检索至某个指针A时，将其混写。按需混写的特点 一个块中的指针需要分次混写，可能会浪费时间不需要的指针不必混写，因而能够节约时间,61,3）显式控制,什么是显式控制 某些应用中，应用程序员可能会知道是否会沿某个块中的指针进行检索。因而可由程序员显式控制。,62,2.4.3 块,主要内容块和记录地址的表示普通记录地址索引结构记录在块中的存储方式BOLB,63,二、记录在块中的存储方式,64,(1)unspanned(2)spanned(3)mixed record types clustering(4)split records,Options for storing records in blocks:,65,records must be within one blockblock 1 block 2.,(1)unspanned,R1,R2,R3,R4,R5,66,Spannedblock 1 block 2.,(2)Spanned,R1,R2,R3(a),R3(b),R6,R5,R4,R7(a),need indicationneed indicationof partial recordof continuation“pointer”to rest(+from where?),67,Unspanned is much simpler,but may waste spaceSpanned essential if record size block size,Spanned vs.unspanned:,68,Example,106 recordseach of size 2,050 bytes(fixed)block size=4096 bytes,Total wasted=2 x 109 Utiliz=50%Total space=4 x 109,69,Mixed-records of different types(e.g.EMPLOYEE,DEPT)allowed in same block e.g.,a block,(3)Mixed record types,DEPT,d1,EMP,e1,EMP,e2,70,Why do we want to mix?Answer:CLUSTERING,Records that are frequently accessed together should bein the same block,71,Compromise:,No mixing,but keep relatedrecords in same cylinder.,72,Example,Q1:select A#,C_NAME,C_CITY,from DEPOSIT,CUSTOMERwhere DEPOSIT.C_NAME=CUSTOMER.C.NAME a block,CUSTOMER,NAME=SMITH,DEPOSIT,NAME=SMITH,DEPOSIT,NAME=SMITH,73,If Q1 frequent,clustering goodBut if Q2 frequentQ2:SELECT*FROM CUSTOMERCLUSTERING IS COUNTER PRODUCTIVE,74,Fixed part in one blockTypically forhybrid formatVariable part in another block,(4)Split records,75,2.4.3 块,主要内容块和记录地址的表示普通记录地址索引结构记录在块中的存储方式BOLB,76,三、BLOB,BLOB的存储BLOB的检索,77,BLOB的存储,存储在一系列块中。即跨块存储。将BLOB存储在磁盘的一个或多个柱面上的连续块中将BLOB存储在块的链表中将BLOB进行分割，存储在几个磁盘中,78,BLOB的检索,只检索记录的非BLOB字段一次一个地请求BLOB块，而与记录的其余部分无关。(eg.观看电影)请求BLOB内的部分，而不必接收整个BLOB。这需要合适的索引结构。(eg.观看或收听视频或音频的某个指定片段),79,2.4 数据组织方式,2.4.1 数据组织方法概述2.4.2 记录2.4.3 块2.4.4 增删改记录,80,2.4.4 增删改记录,1插入记录2删除记录3更新记录,81,1插入记录,记录无序找到有空闲空间的块没有，则找一个新块,82,记录顺序存储需要移动记录能在当前块中为插入记录找到空间在块中移动记录调整偏移量表中的表项插入新记录，并填偏移量表在“邻近块”中找空间将当前块的最高记录移到邻近块中，并移动两个块的中记录当有外部指针指向某个跨块移动的记录时，需要在原位置留下一个“转发地址”创建一个溢出块,83,2删除记录,回收空间的方法移动记录，使块中间总有一个未用空间在块首部维护一个可用空间列表去除溢出块悬挂指针问题,84,Dangling pointers,Concern with deletions,R1,?,85,Physical Ids(对于偏移量表方式）,A blockThis spaceThis space cannever re-used be re-used,Leave“MARK”in map or old location,86,Logical Ids（对于映射表方式）,Leave“MARK”in map or old location,87,3更新记录,更新定长记录对存储系统无影响,88,更新变长记录 新记录比旧记录长 移动记录创建溢出块 新记录比旧记录短 合并空闲空间去除溢出块,89,第二章 RDBMS的物理组织,2.1 存储介质2.2 存储方式2.3 数据表示方法2.4 数据组织方式2.5 索引组织方式2.6 ORACLE和TeraData的数据库结构和体系结构,90,2.5 索引组织方式,索引的好外索引块数量通常比数据块数量少得多可以有有效的方法查找索引（普通索引：二分查找；树形索引：从根到叶；HASH索引：直接计算）索引文件可能足够小，可以永久地存放在内存缓冲区中，从而减少I/O操作,91,几类索引方法排序文件上的简单索引非排序文件上的辅助索引B树及其变种HASH 多属性索引,92,2.5 索引组织方式,2.5.1 顺序文件上的索引2.5.2 辅助索引2.5.3 B树及其变种2.5.4 HASH文件2.5.5 多属性索引,93,2.5.1 顺序文件上的索引,主要内容稠密索引稀疏索引多级索引取重复值属性上的索引索引维护,94,1.稠密索引,什么是稠密索引索引块中存放每条记录的码以及指向记录本身的指针,95,Sequential File,示例,96,Sequential File,Dense Index,示例,97,稠密索引的查找方法二分查找,98,2.稀疏索引,什么是稀疏索引索引块中存放每个数据块中第一条记录的码值及指向该记录的指针。稀疏：每个存储块只有一个索引项。,99,Sequential File,示例,100,Sequential File,Sparse Index,示例,101,稀疏索引的查找方法（查找码为K的记录）首先用二分查找法查找码值小于或等于K的最大码值然后根据它的指针找到相应的数据块在该数据块中搜索，查找码值为K的记录,102,3.多级索引,多级索引的引入索引较小时，可以将其存放到内存或磁盘的预留存储区中，从而使索引查找速度较快。当索引较大时，可以在索引上再建一级索引，并将新的索引本身存放到某个固定的地方，这就是多级索引。通过在索引上再建索引，能够使第一级索引更为有效。二级索引或更高级的索引必须是稀疏索引。,103,Sequential File,示例,104,Sequential File,Sparse Index,示例,105,Sequential File,Sparse 2nd level,示例,106,多级索引的查找方法（查找码为K的记录，以两级索引为例）首先用二分查找法查找二级索引，找到码值小于或等于K的最大码值根据该最大码值对应的指针找到一级索引的相应存储块B若存储块B不在内存，将其读入内存利用一级索引查找码值为K的记录如果一级索引是稠密索引：同稠密索引查找方法如果一级索引是稀疏索引：同稀疏索引查找方法,107,4.取重复值属性上的索引,四种策略 稠密索引：两种策略稀疏索引：两种策略,108,方法一,稠密索引。每一个具有码值K的记录设一索引项。允许索引文件中出现重复的查找码 示例,109,Duplicate keys,110,10,10,10,20,20,30,30,30,10,10,10,20,20,30,30,30,Dense index,one way to implement?,Duplicate keys,111,查找找出具有码值K的第一个索引项，后面紧接着的为其他的具有码值K的索引项。依据这些索引指针可以找到所有具有码值K的记录缺点索引大，可能不能放入内存，从而增加I/O,112,方法二,稠密索引。为所有码值为K的记录只设一个索引项。该索引项的指针指向码值为K的第一个记录。示例,113,10,20,30,40,Dense index,better way?,Duplicate keys,114,查找首先利用索引找到码值为K的第一个记录然后在数据文件中顺序向下查找其他码值为K的记录（必然相邻）,115,方法三,稀疏索引。索引的码-指针对对应数据文件中每个块的第一个查找码。示例,116,10,10,20,30,Sparse index,one way?,Duplicate keys,117,查找首先找到索引中键值小于或等于K的最后一个索引项E1然后向索引起始方向搜索，直到第一个索引项或找到一个严格小于K的索引项E2为止从E2到E1的索引项（含E2和E1）指向所有可能包含码为K的记录的数据块。在这些数据块中顺序查找码为K的记录即可,118,方法四,稀疏索引。为每个数据块中新的（未在前一存储块中出现过的）最小查找码设一索引项。要是在存储块中没有新码值出现，那么就为该块中唯一的码值设一索引项。示例,119,10,20,30,30,Sparse index,another way?,Duplicate keys,place first new key from block,120,查找在索引中查找第一个码值满足如下条件之一的索引项等于K小于K，但下一个码值大于K按照这个索引项的指针找到相应的数据块，在该数据块中查找到码值为K的所有记录。如果其中一个记录为该块的第一条记录，则继续向上查找其他数据块，直到找出所有查找码为K的记录。如果其中一个记录为该块的最后一条记录，则继续向下查找其他数据块，直到找出所有查找码为K的记录。,121,10,20,30,30,example,40,122,5.索引维护,删除从稠密索引中删除某个记录从稀疏索引中删除某个记录 插入 向稀疏索引中插入某个记录向稠密索引中插入某个记录,123,Deletion from dense index,10,20,30,40,50,60,70,80,124,Deletion from dense index,40,30,10,20,30,40,50,60,70,80,delete record 30,125,Deletion from sparse index,10,30,50,70,90,110,130,150,126,Deletion from sparse index,10,30,50,70,90,110,130,150,delete record 40,127,Deletion from sparse index,10,30,50,70,90,110,130,150,delete record 30,128,Deletion from sparse index,10,30,50,70,90,110,130,150,delete records 30&40,129,Insertion,sparse index case,10,30,40,60,130,Insertion,sparse index case,10,30,40,60,insert record 34,131,Insertion,sparse index case,10,30,40,60,insert record 15,Immediate reorganization,132,Insertion,sparse index case,10,30,40,60,insert record 25,133,Insertion,dense index case,Similar Often more expensive.,134,135,2.5 索引组织方式,2.5.1 顺序文件上的索引2.5.2 辅助索引2.5.3 B树及其变种2.5.4 HASH文件2.5.5 多属性索引,136,2.5.2 辅助索引,辅助索引的特点辅助索引的实现技术,137,1.辅助索引的特点,辅助索引不决定数据文件中记录的存放位置，只能指明记录的当前存放位置。辅助索引总是稠密索引。原因：辅助索引不影响记录的存储位置，因而不能根据它来预测码值不在索引中显式指明的任何记录位置。建辅助索引的属性通常取重复值,138,Secondary indexes,Sequencefield,139,Secondary indexes,Sequencefield,Sparse index,140,Secondary indexes,Sequencefield,Dense index,141,With secondary indexes:,Lowest level is denseOther levels are sparse,142,2.辅助索引的实现技术,143,Duplicate values&secondary indexes,144,Duplicate values&secondary indexes,one option.,Problem:excess overhead!disk space search time,145,Duplicate values&secondary indexes,10,another option.,Problem:variable sizerecords inindex!,146,Duplicate values&secondary indexes,Another idea:Chain records with same key?,Problems:Need to add fields to records Need to follow chain to know records,147,Duplicate values&secondary indexes,buckets,148,Why“bucket”idea is useful,IndexesRecordsName:primary EMP(name,dept,floor,.)Dept:secondaryFloor:secondary,149,Query:Get employees in(Toy Dept)(2nd floor),Intersect toy bucket and 2nd Floor bucket to get set of matching EMPs,150,This idea used in text information retrieval,Documents,.the cat is fat.,.was raining cats and dogs.,.Fido the dog.,151,152,153,祝 大 家国 庆 节 快 乐！,154,2.5 索引组织方式,2.5.1 顺序文件上的索引2.5.2 辅助索引2.5.3 B树及其变种2.5.4 HASH文件2.5.5 多属性索引,155,2.5.3 B树及其变种,B树的引入 B树是为解决大型索引的组织和维护而产生的一种数据结构。,156,Conventional indexes,Advantage:-Simple-Index is sequential filegood for scans,Disadvantage:-Inserts expensive,and/or-Lose sequentiality&balance,157,ExampleIndex(sequential)continuousfree space,10,20,30,40,50,60,70,80,90,158,NEXT:Another type of indexGive up on sequentiality of indexTry to get“balance”,159,B树的特点 高效易变平衡对硬件相对独立 B树是索引组织的一种标准形式,160,本节主要内容 基本B树B+树B树的其它变种二分B树B树的并发控制,161,1.基本B树,一棵秩(order)为 n的B树具有下列特征：1.每个结点最多包含n个key。2.除了根结点外，每个结点最少包含n/2个key（根结点最少含有一项）。3.含有j项的结点，有j+1个儿子（叶结点除外，它没有儿子)。4.所有的叶结点都在同一级上。,162,一个含有j项的结点的结构 Ki(1ij)是码，并且kiki+1，Pi是指引元，Pi所指向的子树中码值均小于Ki+1大于等于Ki。在实现时一般在结点中附加一项信息指出结点当前所含有的实际项数j。,163,2.B+树,什么是B+树B树+顺序集,164,Root,B+Tree Examplen=3,100,120150180,30,3511,3035,100101110,120130,150156179,180200,165,Sample non-leaf,to keys to keys to keys to keys 5757 k81 81k95 95,578195,166,Sample leaf node:,From non-leaf nodeto next leafin sequence,578195,To record with key 57To record with key 81To record with key 85,167,Size of nodes:n+1 pointersn keys,(fixed),168,Dont want nodes to be too empty,Use at leastNon-leaf:(n+1)/2pointersLeaf:(n+1)/2 pointers to data,169,Full nodemin.nodeNon-leafLeaf,n=3,120150180,30,3511,3035,counts even if null,170,B+tree rulestree of order n,(1)All leaves at same lowest level(balanced tree)(2)Pointers in leaves point to recordsexcept for“sequence pointer”,171,Number of pointers/keys for B+tree,172,B+树的查找随机查找从根到叶的一条通路。（查找通路）顺序查找随机查找通路的末端结点为顺序查找提供了入口点，从这个入口点开始沿着顺序集就可以进行顺序查找。若是从头开始顺序查找，可以从顺序集的链头SH开始。,173,B+树的维护插入删除,174,Insert into B+tree,(a)simple casespace available in leaf(b)leaf overflow(c)non-leaf overflow(d)new root,175,(a)space available in leaf-Insert key=32,n=3,3511,3031,30,100,176,(b)leaf overflow-Insert key=7,n=3,3511,3031,30,100,177,(c)non-leaf overflow-Insert key=160,n=3,100,120150180,150156179,180200,178,(d)New root-insert 45,n=3,102030,123,1012,2025,303240,179,(a)Simple case(b)Coalesce with neighbor(sibling)(c)Re-distribute keys(d)Cases(b)or(c)at non-leaf,Deletion from B+tree,180,(a)Simple case Delete 30,1040100,102030,4050,n=4,181,(b)Coalesce with siblingDelete 50,1040100,102030,4050,n=4,182,(c)Redistribute keysDelete 50,1040100,10203035,4050,n=4,183,4045,3037,2526,2022,1014,13,1020,3040,(d)Non-leaf coaleseDelete 37,n=4,25,184,删除操作注意,B+索引非叶结点中的码仅仅起到了分隔两棵子树的作用，因而又称为分隔元。对于Ki来说它可以取Pi-1所指向的子树中最大码和Pi所指向子树中最小码（包括该最小码）之间的任何值，而不必是数据记录中实际存在的码值,185,删除操作注意（Cont.),因此B+树的删除总是发生在数据块上，比B树的删除情况单一。只要删除后数据块中的记录数仍有一半以上就不必修改索引项，即使索引项中的码值已实际删去。只有当删除后数据块中的记录数不足一半而要“重新分配”或“合并”时可能要调整索引项或者删除索引项。,186,3.B树的其它变种,降低B树的高度是提高B树效率的关键。降低B树高度两种方法 提高空间利用率尽可能提高秩由此又衍生出不少B树的变种。,187,1)提高空间利用率B*树,B树和B+树的每个结点都规定至少装满一半，存贮空间的利用率为0.5-1.0，平均利用率为0.75。若让结点至少装满2/3以上，则最低空间利用率就由0.5提高到0.66。这样B树的高度得以降低。这种改进后的B树称为B*树。它的查找算法和B树相同，只有插入和删除算法中的“分裂”和“合并”稍有改变。,188,2)增大n值前缀B树和压缩技术,前缀B树压缩技术,189,前缀B树,B+树中索引部分的码值仅仅起分隔左右子树的作用，因而它不必由实际的码组成。为了使一个块中能存放更多的索引项提高B+树的秩以降低B+树的高度，可以选择码的最短一个前缀作为分隔符，这就是前缀B树。,190,191,前缀B树的问题 选择码的最短一个前缀作为分隔符有时并不有效。,192,解决方法 方法1：采用一个算法，扫视邻近的码，取一对具有较短前缀的码作为分隔值。例：在上例中可以选择“prepare”和“programmer”这对码，用“pro”作为它们的分隔值。这样会造成顺序集诸结点中所包含的项不太均衡，有的结点含有较多的项而有的结点中项较少，但一般并不影响总的操作效率。,193,194,解决方法 方法2：采用压缩技术,195,压缩技术,前缀压缩 把码和其紧前一个码首部相同的位数用一个计数器记下而去掉相同部分，这叫做前缀(prefix)压缩。后缀压缩 由于索引项中的码值可以取大于左子树中最大码值而小于（或等于）右子树中最小码值中的任何一个值，利用这个特点可以对码的尾部进行压缩，称为后缀(suffix)压缩。,196,197,压缩技术,指针可以采用基地址加位移代替绝对地址的方法进行压缩。基地址只存贮一次，指针用位移值来表示。位移值比绝对地址小得多，因而节省了存贮空间。压缩技术可以提高结点的秩，但是要耗费一定的CPU 时间来处理码和指引元的压缩和恢复。,198,4二分B树,B树是作为文件的索引组织而引入的，但是它动态平衡的突出优点使人们也想在内存中使用它。由于内存容量小，所以通常是使用“二分B树”，也称为2-3树。二分B树是秩为2的B树，每个结点有1-2个码，2-3个指针在二分B树中，为了节省内存不让B树中的结点空一半，因而用链结构的方法来表示一个结点。,199,200,二分B树,二分B树中右指引元可以指向一个兄弟结点（对应B树中同一结点的右项），也可以指向它的儿子结点。用一个二进制位的0，1加以区分。删除和插入算法要增加许多细节来正确而无遗漏的修改指针，不仅要修改上一级结点中的，而且要修改更高一级中的指针。,201,5.B树的并发控制,例1：甲进程要查找以6为码的记录；乙进程正把记录4插入结点B。甲进程正在读结点A，从结点A它知道此记录应在结点B中。与此同时，乙进程正把记录4插入结点B，引起了B的分裂。因此当甲进程到达结点B时就找不到以6为码的记录了。,202,甲进程正在读结点A，从结点A它知道此记录应在结点B中。,甲进程要查找以6为码的记录；乙进程正把记录4插入结点B。,与此同时，乙进程正把记录4插入结点B，引起了B的分裂。,203,甲进程正在读结点A，从结点A它知道此记录应在结点B中。,甲进程要查找以6为码的记录；乙进程正把记录4插入结点B。,与此同时，乙进程正把记录4插入结点B，引起了B的分裂。,因此当甲进程到达结点B时就找不到以6为码的记录了。,读写冲突,204,例2：甲进程插入2,乙进程删除8甲进程正在把2插入结点C，它记下的查找通路是AB C。乙进程正到达结点E准备把8删去。它形成的查找通路是ABE。甲进程插入完毕后乙进程的返回道路就被破坏了。,205,甲进程插入2,乙进程删除8,甲进程正在把2插入结点C，它记下的查找通路是AB C。乙进程正到达结点E准备把8删去。它形成的查找通路是ABE。,206,甲进程插入2,乙进程删除8,甲进程正在把2插入结点C，它记下的查找通路是AB C。乙进程正到达结点E准备把8删去。它形成的查找通路是ABE。,甲进程插入完毕后乙进程的返回道路就被破坏了。,写写冲突,207,控制并发办法加“锁”但是对于B树来说，仅仅锁住正在处置的那个结点显然是不够了。,208,读操作的封锁方法 一个查找进程可能被干扰的原因当我们刚刚找出了将被查找的子树时，这棵子树或者由于“分裂”使我们