第六章 数据库存储结构.

Presentation on theme: "第六章 数据库存储结构."— Presentation transcript:

1 第六章 数据库存储结构

2 参考书 Raghu Ramakrishnan, Johannes Gehrke, DataBase Management Systems(Second Edition), McGraw-Hill

3 内容提纲 物理存储介质 RAID磁盘系统 DBMS对磁盘空间的管理 DBMS从磁盘读取数据的方法 文件中管理页(page)的方法
页中记录的处理形式 单条记录的存储方式

4 一、物理存储介质 将记录从磁盘读到Buff Pool 缓冲区管理 以记录的文件的形式提供给 文件管理 高层的DBMS进行访问，向
磁盘空间管理器申请或释放 空间 文件管理 磁盘空间管理 控制磁盘上可用的空间

5 第二级存储器（secondary storage）
存储介质层次 磁盘存储器 磁带存储器 光存储器 高速缓存 快闪存 内存 第二级存储器（secondary storage） 第三级存储器（tertiary storage） Primary storage

6 存储结构 分级存储的原因 磁带的特点 价格因素 寻址的问题 数据需要永久保存 价格便宜，存储量大 顺序读取 主存是磁盘的100倍
32位机的主存大小小于232 数据需要永久保存 磁带的特点 价格便宜，存储量大 顺序读取

7 磁盘 基本概念 硬件上的最小单位是sector,是硬件的不可变属性 Block是数据存储的最小单元，由若干sector构成
硬盘上的同心圆构成track 相同半径的同心圆构成Cylinder 存放数据的盘片为Platter 每个面有一个读头，通过磁盘臂进行移动 磁盘转动，读头不动

8 磁盘

9 磁盘 硬盘的容量 磁盘的性能指标 记录盘面数＊每记录盘面的磁道数＊每磁道的盘块数＊每个盘块的字节数 数据的定位信息
柱面号 磁头号 盘块号，系统对盘块进行统一编号 磁盘的性能指标 磁盘容量：10－180，000M 存取时间 Seek time＋Rotational delay＋Transfer time 传输速度：1－5MB/秒 可靠性：3－8万小时

10 磁盘 读写的并行性 磁盘控制器 Checksum 记录的存取方式 一般的系统不支持读头间读取数据的并行性
少数支持有限度的并行，如两个并行，主要原因在于读头无法并行移动 磁盘控制器 负责实现对磁盘的基本操作，如移动读头，定位传输数据等 Checksum 用于检测数据是否正确地读写，读写时各算一遍 记录的存取方式 不跨块方式 跨块方式

11 磁盘结构对性能的影响 DBMS在操作时数据在内存中 磁盘和内存间数据交换的单位是Block,一次传输为一次I/O操作
为了提高速度，最好将同时读写的数据放在接近的地方，如同一block、track、clinder Create tables space……overhead... transfer...

12 第三级存储器 光盘 CD DVD WORM 磁带 胶片

13 RAID磁盘系统 磁盘是数据库管理系统性能的瓶颈 磁盘阵列（Disk Array） 微处理器速度的提高为每年50%
磁盘访问的速度的提高为每年10% 数据传输的速度的提高为每年20% 磁盘阵列（Disk Array） 通过数据条带（Data Striping）分布将多个磁盘变成一个整体 若干磁盘组织在一起，通过并行提高速度 通过冗余提高数据的可靠性 Redundant array of independent disk=RAID

14 数据条带 磁盘间的并行性提高了磁盘组数据读取的性能 数据条带 数据被分成等长的分区，分布在多个盘上，
每个分区的大小为一个条带单元(striping unit)

15 数据冗余 磁盘组可有效提高性能，但降低了可靠性 通过增加数据冗余，即check disk来提高数据可靠性 冗余信息的存放位置
如何计算冗余信息 奇偶校验 Hamming code 数据存放的位置： D1 D2 D3 D4 D5 D6 D7 D8 海明码： C1 C2 C3 C4 C1 = D1 + D2 + D4 + D5 + D7 C2 = D1 + D3 + D4 + D6 + D7 C3 = D2 + D3 + D4 + D8 C4 = D5 + D6 + D7 + D8 Reed-Solomon Code

16 RAID LEVEL RAID LEVEL 0：Nonredundant
没有冗余数据 可靠性差 写性能最优，读性能却不是最优 空间利用率100%

17 RAID LEVEL LEVEL 1：Mirrored LEVEL ０＋１：Striping and Mirroring
最昂贵的一种方法，每个磁盘都由一个备份 每次写两遍，同一块数据可并行读 空间利用率５０% LEVEL ０＋１：Striping and Mirroring 以Ｍirrored的方法为基础，增加数据分布的条带化 各种性能与Level1相似

18 RAID LEVEL LEVEL 2：Error-Correcting Code
Striping unit 是一位 冗余模式为Hamming Code Check disk的数量是数据盘的数量的对数 读操作一次D块,D为数据盘的数量 写操作遵循read-modify-write cycle LEVEL 3：Bit-Interleaved Parity 冗余模式为奇偶校验 Check disk的数量是１

19 RAID LEVEL LEVEL 4：Block-Interleaved Parity
Striping unit 是一块 冗余模式为奇偶校验 Check disk的数量是１ 写操作遵循read-modify-write cycle，但只需读一块 LEVEL 5： Block-Interleaved Distributed Parity 基本想法与Level４相同 冗余信息分布在不同的盘上，避免check disk成为瓶颈 性能最好

20 RAID LEVEL LEVEL 6：P+Q redundancy Raid level的选择 以Level 5为基础
在大量盘的情况下，防止两个盘同时出错 采用Reed-Solomon冗余模式，有2个Check disk Raid level的选择 Level0代价小 Level 0+1适用于小型系统或大量写的系统 Level 3适用于大规模连续读、写的系统，优于Level 2 Level 5各种情况性能均不错，优于Level 4 Level 6适用于高可靠性系统

21 磁盘空间管理 DBMS结构的最底层 以页为单位组织数据，主要操作包括读、写、申请和释放 经常访问的数据可放在连续的空间中
隔离上层模块和底层的软、硬件平台

22 磁盘空间管理 管理空闲块的方法 实现方法 记录哪些块正在使用，每一页的位置 通过一个空闲块链表或空闲块位图来记录空闲的块
利用操作系统文件系统管理磁盘空间 自己实现对磁盘的访问 选择的因素 跨平台的要求 有的功能操作系统不提供

23 缓冲区管理器 负责将磁盘上的数据读入内存并写回磁盘的软件层 管理器管理的内存空间称为Buffer Pool
Buffer Pool中的每个页称为Frame(每个Frame包含若干slot) 如Buffer Pool有10个页，表中有100个页，如何进行扫描工作 决定内存中那些页应该被替换的策略称为Replacement Policy

24 工作流程 高层代码的页请求 高层代码的页请求 正在访问的frame Buffer Pool Buffer Pool Dirty Frame
Free Frame Free Frame 已访问完且未被 修改的数据 如果所需的页不在Buffer Pool中且Buffer Pool已满 则用Replace Policy 进行调度 DB DB

25 数据结构和流程 每个frame包括：pin_count,dirty 请求处理的流程 pin_count:正在访问该frame的事务的个数
Dirty:已经被修改过的Frame 请求处理的流程 查看Buffer pool是否包含此页，如没有，则 找一个pin_cout为０的frame，pin_cout++ 如dirty为true,则将其写入磁盘 将相应的页读入此frame 将frame的地址返回

26 几点补充 Dirty代表此frame的数据已被修改，在Dirty frame被替换之前需要同步到磁盘上
申请新的frame时如没有可替换的frame，则等待 如何处理多个事务同时访问一个frame中的数据？

27 缓冲区的替换策略 最早使用策略(Lest recently used,LRU) Clock策略
当pin_count=0时该frame成为可选择，但并不是马上被替换，因为在此之前有可能再次被访问 最早变成可选择的页被首先替换 Clock策略 将所有的frame排成一个圈，下一个被替换的页是圈上的下一个可选择的页 使用referenced标志避免刚被访问过的frame被再次访问，其想法是referenced在第一遍访问时变成true，第二遍才替换

28 缓冲区的替换策略 实际系统中的Buffer Pool DB2：clock,允许有多个Buffer Pool
Sybase ：LRU,允许有多个Buffer Pool Informax,Oracle: LRU,单个Buffer Pool Sql Server: clock,单个Buffer Pool

29 Buffer Pool的预取 Buffer Pool与virtual memory
页访问模式产生的原因在于，页的访问方式由上层的查询代数和操作决定 页的预取 DB2中的Prefetching dirty frame的强制写盘

30 文件与索引 每个页中包含若干条记录，每个文件中包含若干个页 每个记录有一个唯一的标识符:rid，它包括页号和在页中的位置

31 堆文件 数据在文件中以记录为单位无序地存储，是最简单的文件形式 提供的功能包括：创建、删除文件，插入删除记录 需要讨论的问题
记录页中的空闲区间 记录有空闲区间的页 如何维护文件空闲区域的位置 页的链表 页字典

32 页的链表 每个文件记录其第一个页 该页连接两条链表 缺点 对非定长记录则全在空链表中 含空闲区间 的页 …. 数据页 数据页 数据页 头表
不含空闲区间 的页 数据页 数据页

33 页字典 用一个字典记录每个页的信息，包括空闲的空间大小 字典的长度相对数据部分较小 分配空间前将字典读入 头页 数据页1 数据页2 ….
数据页n 字典

34 顺序文件 根据查找键的值的顺序存储记录的文件 每个记录有一个指针，按键值大小创建链表 通过自由空间管理，管理空闲空间 He F-257
800 Liu A-102 600 Zhou C-343 750

35 顺序文件 插入操作 删除操作 He F-257 800 Liu A-102 600 Zhou C-343 750 Ma B-547 500
寻找插入位置 申请空闲空间 维护链表 删除操作 He F-257 800 Liu A-102 600 Zhou C-343 750 Ma B-547 500

36 聚集文件 一个文件中存储多个关系中的元组 根据键属性进行数据组织 S1 Wang 20 C1 C2 80 70 S2 Liu 21 S3
Chen 22 C3 90 85 95 M S1 C1 80 S1 C2 70 S3 C1 90 S3 C2 85 S3 C3 95 F S1 Wang 20 M S2 Liu F S3 Chen 22 M M S SC

37 代价模型 代价用与于估算不同的查询操作的代价 基本的符号 B:数据库中数据页的数量 R:每页中记录的个数 D:读写一页的时间
C:处理一条记录的时间（对相应的属性进行比较） H:对一条记录执行执行Hash函数的时间

38 代价计算的单位 磁盘读写操作和计算的代价差巨大 本书采用磁盘页的读写作为代价标准 D=15毫秒，C,H=100纳秒 上述差距将越来越大
在本书只是讨论影响操作的主要因素 本书没有讨论块的读写问题，由于一块上有若干页，而且是硬件操作的基本单位。但页是DBMS系统的读写单位，所以选用了页

39 三种文件组织方式的比较 三种文件组织方式 Search Key:用于排序和Hash的列 随机排序文件，堆文件 对一系列属性进行排序的文件

40 基本操作 Scan Search with equality selection Search with range selection
读取文件中所有的记录 Search with equality selection 读取文件中满足某一相等条件的记录 Search with range selection 读取文件中满足区间条件的记录 Insert 将特定记录插入文件 Delete 将特定记录从文件中删除

41 堆文件 Scan Search with equality selection Search with range selection
代价为B(D+RC) Search with equality selection 如事先知道只有一个结果，则为0.5B(D+RC),否则同Scan Search with range selection Insert 2D+C(数据加在关系的最后面) Delete D+C(数据已经在内存中，可用rid中的page id访问)

42 排过序的文件 Scan Search with equality selection Search with range selection
代价为B(D+RC) Search with equality selection 代价为Dlog2B+Clog2R(没有重复的情况，且对查询属性排序) Search with range selection 同上 Insert B(D+RC)(数据是连续存放的情况) Delete

43 Hashed的文件 文件被分解为筐(Bucket) 通过一个Hash函数找到相应的筐 需要考虑溢出的情况 Bucket1 Hash函数

44 Hashed的文件 Scan Search with equality selection
代价为1.25B(D+RC)(由于在文件中保存了一定的空闲) Search with equality selection 代价为H+D+0.5RC(只有一个结果) Search with range selection 代价为1.25B(D+RC) Insert 代价为2D Delete 代价为C+D

45 页的格式 页由一系列的记录构成 每个记录为一个slot 记录的id为(page id, slot number)

46 记录格式 记录格式 定长记录 变长记录 系统catalog中记录了相关的信息

47 定长记录 每条记录的长度是固定的，即没有变长字段，一个页存放记录的数量和位置也是确定的 删除方法

48 定长记录 Packed Unpacked ... ... 每次删除了记录就将该页最后一 条记录移到被删除的位置，所有
slot1 slot1 slot2 slot2 ... 空闲空间 ... slotn slotn 记录数 记录数 n ……. 0 1 m m m 每次删除了记录就将该页最后一 条记录移到被删除的位置，所有 的空闲空间均在页的下部，但rid 会不断调整 每次删除了记录不做移动，所有 的空闲空间的信息记录在页的尾部

49 定长记录 数据连续存放 每个字段有固定的位置 各种数据的方法基本相同 Fi=field i F1 F2 F3 F4 …..
L L L3 L4 Base address(B) Address=B+L1+L2+L3 Li=Length of field i

50 变长记录 记录中包含变长字段，所以记录的长度是可变的 无法分配定长的slot 为了避免大量的零碎空间，每次删除后需要对页上的空间进行调整。
但是要保证rid不变 解决方法：用slot字典存放记录的起始位置和记录的长度，用记录在slot字典中的位置代替slot的实际起始位置

51 变长记录 数据页i 记录（i，n） 记录（i，1） 记录（i，2） n Slot字典 页中slot数量

52 变长记录 两种存放方法 数据连续存放用分割符分开：需要扫描无用信息 在记录的前端用指针指向响应的位置
F1 $ F2 $ F3 $ F ….. Fi=field i F F F F4

53 变长记录 对一个列的修改需要移动其它列的位置
一条记录修改后可能造成记录的长度超过目前该页所能提供的空间，需要存入其它的页，为了保证rid不变需要记录该记录的目前位置 如长度超过一个页的大小，则要分页 实际系统中 Oracle不限制记录长度 DB2等限制长度，但提供大对象数据类型

54 文件组织和索引 文件组织是当文件存储在磁盘上时在文件中组织记录的方法 不同的方法有不同的作用 索引是查询操作的性能的工具

55 在实际系统可能并不是完全排序，也不是完全的连续存放
文件组织形式的选择 在实际系统可能并不是完全排序，也不是完全的连续存放

56 索引简介 索引是加速查询操作的辅助文件结构 对要访问的属性值进行重新组织，每个索引项包含（属性值，rid） 包括树型索引和Hash索引
一个索引可认为是一个data entry的集合，通过它可快速地找到相应的记录所在的位置 需要考虑的两个问题 为了方便查询如何组织data entry data entry的构成

57 索引的例子 h1 h2 File of <sal,rid> File hashed on age
Smith,44,3000 3000 H(age)=00 Jones,40,6003 3000 H(sal)=00 Tracy,44,5004 5004 5004 age Ashby,25,3000 H(age)=01 sal h1 h2 Basu,33,4003 4003 Bristow,29,2007 2007 6003 Cass,50,5004 H(sal)=11 H(age)=10 6003 Daniels,22,6003 File hashed on age File of <sal,rid> pairs hashed on sal

58 索引中各种不同的data entry 三种类型 用k*就没有必要再存储相应的记录，所以可作为一种特殊的文件组织形式
<k,rid>search key为k的记录 <k,rid-list>search key为k的记录集合 用k*就没有必要再存储相应的记录，所以可作为一种特殊的文件组织形式 <k,rid><k,rid-list>两种方式广泛地应用于各种索引结构，特别是一个表上不只有一 个索引的情况

59 索引的特性 Clustered versus UnClustered Indexes Dense versus Sparse Indexes
Primary versus Secondary Indexes Composite Search key 的索引

60 Clustered versus UnClustered Indexes
如果文件中记录的次序同索引中data entry的次序是相同的，则这个索引是Clustered(簇聚的) 第一种data entry是Clustered 只有当记录的顺序用索引对应的属性排序时，第二、三种data entry对应的索引才是clustered

61 Clustered versus UnClustered Indexes
一个表只有一个Clustered索引多个unclustered索引 鉴于高昂的维护代价，即使是一个 Clustered索引也经常是不严格排序的 用溢出链表的形式 定期重新排序 update操作与Clustered 对Range查询Clustered的作用比较大

62 Clustered Indexes Index entry Index file Data entry ... ... Data file
Data Records

63 UnClustered Indexes Index entry Index file Data entry ... ...
Data file Data Records

64 Dense versus Sparse Indexes
如果表在该属性上出现的所有值在索引文件中均至少有一个data entry与之相对应则为dens索引。Sparse索引中每个页有一个data entry 第一种 data entry只能用于dense索引 第二种 data entry能用于两种索引 第三种 data entry通常用于dense索引 Sparse索引只能是Clustered的索引

65 例子 Sparse index on name DATA Dense index on age Ashby,25,3000 22
Basu,33,4003 25 Ashby Bristow,30,2007 30 Cass 33 Smith Cass,50,5004 Daniels,22,6003 40 Jones,40,6003 44 44 Smith,44,3000 50 Tracy,44,5004 Sparse index on name DATA Dense index on age

66 Primary and Secondary Indexes
如果索引建在包含Primary Key的属性上则为Primary Index，其它的为Secondary Index 另一种解释为第一种data entry对应的索引为Primary Index,另两种为Secondary index 如果两个data entry在索引属性上对应的值是相同的，则该索引为duplicates index,否则为unique index

67 Composite Search key 的索引
Index <age> Index <age,sal> 11 12 11,80 12 12,10 Name age sal 13 12,20 Bob 13,75 Cal Joe Index <sal> Sue Index <sal,age> 10 20 10,12 75 20,12 80 75,13 80,11

68 索引的定义 在SQL-92中并没有关于索引的语句，在SQL中也没有涉及索引 所有的商用DBMS均提供了与索引相关的语句
CREATE INDEX IndAgeRating on Student WITH STRUCTURE=BTREE KEY=(age,gpa)

69 树结构索引 索引提供高效查询操作方法和动态维护方法 ISAM B+TREE 是一种静态的索引结构，适用于数据库变化不大的情况
是一种动态的索引结构，适用于各种情况

70 索引序列访问方法(ISAM) 例子：在排序的文件中做range查询“找gpa超过3.0的学生” 创建一个二级文件作为索引
对整个文件做两分法查找，找到起始的学生的位置 从此位置起读取数据 创建一个二级文件作为索引 记录每一页的起始记录的属性值 索引中元素的格式为(页中第一个键，指向页的指针)

71 索引序列访问方法(ISAM) 二级文件的好处 空间小 速度快 k1 k2 …... kn Page1 Page2 Page3 …...
PageN 二级文件的好处 空间小 每个页只取一个记录 每个记录只取一个属性 速度快

72 索引序列访问方法(ISAM) ISAM的想法 ISAM的构造方法 对每一层二级文件均建立相应二级文件结构 在最底层使用溢出链表
索引中一结点的大小同一个物理页的大小相同 关系中所有的数据均存放在叶子结点 也可以在实际数据上层增加一个第二种类型的data entry 树的结构是静态的，只有叶结点中溢出结点会变化

73 ISAM索引结构示意图 非叶子结点 叶子 结点 ... ... Primary page Overflow page

74 ISAM的基本操作 搜索(单个值查询和区间查询) 插入 删除 从树的根结点开始 每次找下层的相应结点，直到找到结果 取出所有结果
找到相应的位置 插入数据，如果页满了，则增加溢出页 删除 删除数据，如果溢出页空了，则删除溢出页

75 例子 40 10* 15* 20* 27* 33* 37* 40* 46* 51* 55* 63* 97* 原始状态

76 例子 40 10* 15* 20* 27* 33* 37* 40* 46* 51* 55* 63* 97* 23* 48* 41* 42* 插入操作后的情况

77 例子 40 10* 15* 20* 27* 33* 37* 40* 46* 55* 63* 23* 48* 41* 删除操作后的状态

78 ISAM 各项操作的计算复杂性 搜索操作的复杂性为：logFN,F是每个结点中的data entry的数量，N为关系中的记录数，二分法搜索的复杂性为log2N 例子：1,000,000条记录，每页10条记录。每个结点100个data entry,则顺序搜索为100,000,直接二分法为17，一层的索引(采用二分法)为10，ISAM为3

79 几点考虑 插入删除问题 ISAM的并行性 插入删除操作只对叶子层的数据起作用
当连续在同一结点插入时会造成溢出链过长，从而影响查询性能（是顺序查找） 解决方法：创建索引时增加一些空闲空间 ISAM的并行性 非叶子结点不动将修改限制在最下层，索引并发控制比较简单 相比其它索引结构速度快

80 B+树一种动态的索引结构 静态方法的缺点在于当插入删除过多时造成溢出链过长，影响效率。也不利于序列连续存放 M阶B+树的特点
每个结点至多有m棵子树，至少有[m/2]棵子树 根结点或为叶结点，或至少有两棵子树 在insert,delete操作中树保持平衡 搜索时只需要访问树的高度次 所有叶结点在同一层次，data entry层用双向链表连接，便于访问

81 B+树的结构 Index entry Index file Data entry ...

82 B+树索引结点的结构 B+树结点的格式同ISAM的结构相似 每个结点由n个数值和n+1个指针构成
pi指向的子树上的结点的值k,有ki<=k<=ki+1 通常用第二种或第三种data entry Data Entry 本身可以看成为是记录的文件，如果data entry包含整个记录，则文件就是数据本身，否则是一个单独的文件。

83 搜索 Func tree_search(nodepointer, search key value K) returns nodepointer If *nodepointer is a leaf, return nodepointer; else, if K<K1 then return tree_search(P0,K) if K>Km then return tree_search(Pm,K) find i such that Ki<=K<Ki+1; return tree_search(Pi,K); Endfunc

84 B_树的例子 d=2 13 17 24 30 2* 3* 5* 7* 19* 20* 22* 33* 34* 38* 39* 24* 27*
2* 3* 5* 7* 19* 20* 22* 33* 34* 38* 39* 24* 27* 29* 14* 16*

85 Insert 首先从根结点出发向下，找到插入数据所在的位置。 将数据插入到相应的位置。 当结点满的时候，进行分解操作。
逐层向上分解直到不需要分解的时候。 当结点满时另一种方案是：当该结点的兄弟结点不满时，也可以进行重新分配，以减少分解的数量。

86 Insert Proc Insert(nodepointer,entry,newchildentry)
If *nodepointer is a non-leaf node,say N find I such that Ki<=entry’s key value <Ki+1 insert(Pi,entry,newchildentry) if newchildentry is null, return; else, if N has space put*newchildentry on it, set newchildentry to null, return; else split N; first d key values and d+1 nodepointers stay, last d key values and d+1 nodepointers move to new node N2, newchildentry=&(<smallestkey value on N2,pointer to N2>)

87 insert if N is the root create new node with <pointer to N,*newchildentry> make the tree’s root-node pointer point to the new nodes return; If *nodepointer is a leaf node, say L if L has space put entry on it,set newchildentry to null, and return; else split L: first d entries stay, rest move to brand new node L2; newchildentry=&(<smallestkey value on L2,pointer to L2>); set sibling pointers in L and L2 Return ; Endproc

88 例子 增加8以后 17 2* 3* 14* 16* 24* 27* 29* 5* 7* 8* 19* 20* 22* 33* 34* 38* 39*

89 重新调整的例子 增加8以后 8 17 24 30 2* 3* 5* 7* 19* 20* 22* 33* 34* 38* 39*
2* 3* 5* 7* 19* 20* 22* 33* 34* 38* 39* 24* 27* 29* 8* 14* 16*

90 删除 首先从根结点出发向下，找到删除数据所在的位置。 将数据相应的位置删除。 当结点过空的时候，进行合并操作。
逐层向上合并直到不需要合并的时候。 当该结点的兄弟结点不空时，可以考虑重新分配，以减少合并的数量。该调整不仅作用在页结点上，也可作用在非页结点上

91 删除 Proc delete(parentpointer,nodepointer,entry,oldchildentry)
If *nodepointer is a non-leaf node,say N find i such that Ki<=entry’s key value <Ki+1 delete(nodepointer,Pi,entry,oldchildentry) if oldchildentry is null, return; else, remove *oldchindentry from N if N has entry to spare set oldchildentry to null, return; else get a sibling S of N; if S has extra entries redistribute evenly between N and S through parent set oldchildentry to null, return

92 删除 else merge N and S/*M is the new node*/
oldchildentry=&(current entry in parent for M) pull splitting key from parent down into node on left Move all entries from M to node onleft; discard empty node M, return If *nodepointer is a leaf node, say L if L has entries to spare remove entry, set oldchindentry to null, and return; else get a sibling S of L if S has extra entries redistribute evenly between L and S; find entry in parent for node on right replace key value in parent entry by new low-key valuein M; set oldchildentry to null,return else, merge L and S oldchildentry=&(current entry in parent for M); Move all entries from M to node on left discard empty node M, adjust sibling pointers,return Endproc

93 例子 删除19和20以后 17 2* 3* 14* 16* 27* 29* 5* 7* 8* 22* 24* 33* 34* 38* 39*

94 例子 删除24以后 2* 3* 14* 16* 33* 34* 38* 39* 22* 27* 29* 5* 7* 8*

95 重复数据 在某些情况下，索引建立的列上有重复数据 若采用第二种data entry 若采用第三种data entry
修改相应的查询算法，找到最右边的同值记录 若采用第三种data entry 是一种比较直接的处理方法，但在重复数据较多的情况下，要考虑相应的查询和修改算法 SYBASE中采用第三种data entry,DB2,Oracle 8,SQLServer采用增加RID的方法处理重复数据

96 实际应用领域中的B+tree 索引值的压缩
数据库查询的代价是索引树的高度，索引树的高度为logfan-out(#of data entries) Fan-out的值同一个页中存储的数据项的值是相关的。因此需要考虑如何降低数据值的长度。 对字符串可以采用前序串压缩的方法，其基本原理是对每个非页结点字符串值，只取其前缀，但截取以后的值一定要大于其左面子树的所有结点的值，小于其右面子树的所有结点的值

97 前缀压缩的例子 Daniel Lee David Smith Devarakonda …….
Dante Wu Darius Rex ……. Davey Jones “David Smith”只能压缩成“Davi”

98 实际系统中的删除操作 在Sybase中被删除的数据可以被马上删除，也可以先做标签，将来再删除
在Oracle 8中被删除的数据先做标签，将来再调整 在Informax中被删除的数据被加上标签 在DB2,SQLSERVER中被删除的数据被马上删除

99 B+ tree的批量建立 有些情况下需要对已经收集好数据集合建立B+tree 采用逐条加入的方法性能太差 可采用批量建立的方法
收集所有的data entry 首先将所有的data entry排序，并组织成页 每页取出一个值，插入到已建成的索引树的最右端的节点中。逐个进行直到所有的数据被插入为止

100 例子 Root 3 * 4* 6 * 9* 10 * 11* 12 * 13* 20* 22* 23 * 31* 35 * 36*
3 * 4* 6 * 9* 10 * 11* 12 * 13* 20* 22* 23 * 31* 35 * 36* 38* 41* 44*

101 例子 Root 6 10 12 * 13* 20* 22* 23 * 31* 3 * 4* 6 * 9* 10 * 11* 35 * 36*
12 * 13* 20* 22* 23 * 31* 3 * 4* 6 * 9* 10 * 11* 35 * 36* 38* 41* 44*

102 例子 Root 10 6 12 3 * 4* 6 * 9* 10 * 11* 12 * 13* 20* 22* 23 * 31* 35 * 36* 38* 41* 44*

103 基于Hash的索引结构 基于 Hash的索引结构适用于相等查询操作
其基本想法是将数据映射成一个bucket， bucket对应相应数据的存储位置 有各种不同的基于Hash的索引结构 基于 Hash的索引结构不适合区间查询 但Hash方法广泛地应用于数据库的查询操作

104 内容提纲 静态的Hashing 可扩展的Hashing 线性的Hashing 可扩展的Hashing同线性的Hashing的比较

105 静态的Hashing 包含数据的页构成一系列的bucket，每个bucket又一个primary bucket page和一串overflow page构成，overflow page中的数据可以进行排序 查询的过程时首先对查询的数据用Hash函数进行运算，根据结果找到相应的primary page，然后在primary page和overflow page中找相应的记录 插入和删除操作均是基于查询操作实现的 Hash函数的选择是一个非常重要的问题，需要将数据库中的数据均匀地分布在一定的区域上，有很多种不同的Hash函数，例如 H(value)=a*value+b

106 静态的Hashing 静态的Hashing的一个主要的问题是primary bucket page的数量 如果始终不变，则会 解决方法
随着数据库中数据的增加，overflow page串会越来越长，从而影响查询操作的性能。 随着数据库中数据的减少， primary bucket page 会浪费过多的空间 解决方法 定期进行刷新 采用动态的Hashing的方法

107 静态的Hashing …… …… …… h …… Primary Overflow Bucket Pages Pages 1 key N-1
h(key) mod N 1 …… …… key h …… N-1 Primary Bucket Pages Overflow Pages

108 可扩充的Hashing 基本想法是 通过一个directory来记录每个bucket所处的位置
随着数据的增加，bucket将分解，而不是增加overflow页 随着bucket的分解，相应的directory会增长 利用Hash函数结果的最后若干位作为确定bucket的依据 在directory和bucket上分别标有global depth和Local depth作为判断的长度

109 例子 Local Depth 2 Global Depth 4 * 12* 32* 16* 2 2 00 01 1* 5* 21* 10
4 * 12* 32* 16* 2 2 00 01 1* 5* 21* 10 11 2 10* directory 2 15 * 7* 19* bucket

110 例子 Local Depth 2 Global Depth 4 * 12* 32* 16* 增加了entry r H(R)=13 2 2
4 * 12* 32* 16* 增加了entry r H(R)=13 2 2 00 01 1* 5* 21* 13* 10 11 2 10* 2 15 * 7* 19*

111 例子 Local Depth 3 32* 16* Global Depth 2 增加了entry r 3 H(R)=20
32* 16* Global Depth 2 增加了entry r H(R)=20 3 1* 5* 21* 13* 000 001 2 010 10* 011 100 2 101 15 * 7* 19* 110 3 111 4 * 12* 20*

112 例子 Local Depth 3 32* 16* Global Depth 3 3 1* 9* 增加了entry r H(R)=9 000
32* 16* Global Depth 3 3 1* 9* 增加了entry r H(R)=9 000 001 2 010 10* 011 100 2 3 101 15 * 7* 19* 110 5* 21* 13* 3 111 4 * 12* 20*

113 几个需要考虑的问题 Bucket每进行一次分解，对应的local depth 加把directory可以放到内存中，则将大大提高整个查询的性能，每次查询只需要做一次数据库的读操作 如果Hash函数分配不均匀会造成directory急剧增加，所以需要找到好的Hash函数

114 线性Hashing 线性Hashing是一种动态Hashing 它是有一个bucket的序列构成
每个bucket还附带一串overflow page 克服可扩充的Hashing在数据倾斜情况下分解过于频繁的缺点 没有directory 每次只对一个bucket进行分解，激发分解的条件是数据库中有一个bucket进行了分解或增加了新的bucket page。

115 线性Hashing Hash函数类似于：hi(value)=h(value)mod(2iN) hi覆盖的范围是hi+1的1/2
Next指针值向下一个要进行分解的bucket 新分解出的bucket放在bucket序列的最后面 查询时首先根据hi找到相应的bucket和overflow page，然后根据同next的关系，到hi+1指定的bucket和overflow page中去找 随着数据的增加hi中的i不断增加

116 例子 hlevel 新分解的bucket

117 例子 h1 h0 Level=0 N=4 Next=0 000 00 32* 44* 36* 001 01 9* 25* 5* 010 10
32* 44* 36* 001 01 9* 25* 5* 010 10 14* 18* 10* 30* 011 11 31* 35* 7* 11* Primary bucket Pages

118 例子 h1 h0 Level=0 N=4 000 00 32* Next=1 001 01 9* 25* 5* 010 10
9* 25* 5* 010 10 14* 18* 10* 30* 011 11 31* 35* 7* 11* 43* 100 00 44* 36* 增加了记录r有h(r)=43后

119 例子 h1 h0 Level=0 N=4 000 00 32* Next=1 001 01 9* 25* 5* 37* 010 10
9* 25* 5* 37* 010 10 14* 18* 10* 30* 011 11 31* 35* 7* 11* 43* 100 00 44* 36* 增加了记录r有h(r)=37后

120 例子 h1 h0 Level=0 N=4 增加了记录r有h(r)=29后 000 00 32* 001 01 9* 25* Next=2
9* 25* Next=2 010 10 14* 18* 10* 30* 011 11 31* 35* 7* 11* 43* 100 00 44* 36* 101 01 5* 37* 29*

121 例子 h1 h0 Level=0 N=4 增加了记录r有 h(r)=22,66,34后 000 00 32* 001 01 9* 25*
9* 25* 010 10 66* 18* 10* 34* Next=3 011 11 31* 35* 7* 11* 43* 100 00 44* 36* 101 01 5* 37* 29* 110 10 14* 30* 22*

122 例子 h1 h0 Next=0 000 00 32* 001 01 9* 25* 66* 18* 10* 34* 010 10 50* 011 11 43* 35* 11* 100 00 44* 36* Level=0 N=4 101 01 5* 37* 29* 增加了记录r有 h(r)=50后 110 10 14* 30* 22* 111 11 31* 7*

123 可扩展的Hashing同线性的Hashing的比较
当Hash函数比较均衡的时候，两者相差不大，线性的Hashing的比较少了一次读取directory的时间 当Hash函数不均衡的时候 线性的Hashing的primary bucket的数量增长较慢，由于overflow串较长，所以查询性能较差，但空间少 可扩展的的Hashing的primary bucket的数量增长较快由于overflow串较短，所以查询性能好，但占用空间大，如果采用NULL指针，有可能减少空间。

124 多键索引 单键查询的问题 Select eno From employee Where ename=‘liu’ and salry=600
使用ename索引把‘liu’的记录全部找出，再检查每个找的记录salary是否是600 使用salary 索引把600的记录全部找出，再检查每个找的记录ename是否是‘liu’ 使用ename索引把‘liu’的记录全部找出，再使用salary 索引把600的记录全部找出，通过两个集合的交集求得最后的结果 问题：得到的中间结果过多

125 网格文件 Bi TANG NIAN HAO DING 桶 Bi 600 800 1200 1400 1600 2000

126 分区散列技术 在多个属性上建立索引结构 查询键值 散列值 （S4，C4） 0100 0100 0011 0110 0010 0111