Sequential File 10 20 30 40
Item: (Search key, Pointer to block)
50 60
70 80 90 100
chapter 4
7
• 稀疏索引的查找方法（查找码为K的记录）
–首先用二分查找法查找码值小于或等于K的最大码值 –然后根据它的指针找到相应的数据块 –在该数据块中搜索，查找码值为K的记录
42
90 ...
does not make sense!
chapter 4
Secondary indexes
• Dense index
10 50 90 ... 10 20 30 40 50 60 70 ...
• 1 000 000元组 ,4096/块,10个元组/块, 100 000块,400M
100个索引项/块, 10 000块, 40M
chapter 4 6
3.1.3 Sparse Index
One item for each Block
10 30 50 70 90 110 130 150 170 190 210 230
chapter 4
27
3.1.6 索引维护
数据文件的变化必须相应的对索引文件进行维护 按照顺序文件记录的插入和删除（3.5）算法
• 删除
– 从稠密索引中删除某个记录 – 从稀疏索引中删除某个记录
• 插入
– 从稀疏索引中插入某个记录
– 从稠密索引中插入某个记录
chapter 4
28
Deletion from dense index
place first new key from block
10 20 30 30
10 10
10 20
20 30 30 30 40 45
chapter 4 26
• 查找
–在索引中查找第一个码值满足如下条件之一的索引项 • 等于K • 小于K，但下一个码值大于K –按照这个索引项的指针找到相应的数据块，在该数据 块中查找到码值为K的所有记录。 • 如果其中一个记录为该块的第一条记录，则继续 向上查找其他数据块，直到找出所有查找码为K的 记录。 • 如果其中一个记录为该块的最后一条记录，则继 续向下查找其他数据块，直到找出所有查找码为K 的记录。
– delete records 30 & 40
10 50 30 70 50 70
10 20
30 40
50 60 70 80
90 110 130 150
chapter 4
34
Insertion, sparse index case
10 30 40 60
10 20
30
40 50 60
chapter 4
30
Deletion from sparse index
10 20
10 30 50 70
30 40
50 60 70 80
90 110 130 150
chapter 4
31
Deletion from sparse index
– delete record 40
10 30 50 70
10 20
30 40
15
Duplicate keys
10 10
10 20
20 30 30 30 40 45
chapter 4 16
Duplicate keys
Dense index, one way to implement?
10 10 10 20
10 10
10 20
20 30 30 30 40 45
chapter 4 17
第三章 索引结构
chapter 4
1
Topics
3.1 3.2 3.3 3.4 顺序文件上的索引 辅助索引 B-树索引 多维索引
chapter 4
2
Select * from student
//全表扫描，查找每一个块，找每一个记录
Select sname from student where sno=200415006
chapter 4
24Biblioteka 策略四• 稀疏索引。为每个数据块中新的（未在 前一存储块中出现过的）最小查找码设 一索引项。要是在存储块中没有新码值 出现，那么就为该块中唯一的码值设一 索引项。 • 示例
chapter 4
25
Duplicate keys
Sparse index, another way?
sort key 、 primary key 、 Foreign key、 。。。
chapter 4
50 60 70 80
90 100
4
3.1.2 Dense Index
One item for each Record
Item: (Search key, pointer to record)
10 20 30 40 50 60 70 80 90 100 110 120
chapter 4
12
Summary
• • • • • • • Index sequential file Search key ( primary key) Primary index (on Sequencing field) Secondary index Dense index (all Search Key values in) Sparse index(only one key for a block) Multi-level index
Sequential File 10 20 30 40 50 60 70 80
90 100
chapter 4
5
索引的好处
• 索引块数量通常比数据块数量少得多 • 有效的方法查找索引
– 普通索引：二分查找； – 树形索引：从根到叶； – HASH索引：直接计算
• 如果索引文件足够小，可以永久地存放在内存缓 冲区中，从而减少I/O操作
• 辅助索引的实现技术
chapter 4 40
Sequence field
30 50 20 70 80 40 100 10 90 60
chapter 4 41
Secondary indexes
• Sparse index
30 20 80 100
Sequence field
30 50 20 70 80 40 100 10 90 60
chapter 4 13
3.1.5 Indexes with Duplicate search keys • 四种策略
–稠密索引：两种策略 –稀疏索引：两种策略
chapter 4
14
策略一
• 稠密索引。每一个具有码值K的记录设一 索引项。允许索引文件中出现重复的查 找码 • 示例
chapter 4
– insert record 15
10 20 30 40 60
10 20 15
30 20 30
40 50 60
•Immediate reorganization
chapter 4
37
Insertion, sparse index case
– insert record 25
10 30 40 60
10
多级索引的查找方法
（查找码为K的记录，以两级索引为例） • 首先用二分查找法查找二级索引，找到码值小于或等 于K的最大码值 • 根据该最大码值对应的指针找到一级索引的相应存储 块B • 若存储块B不在内存，将其读入内存 • 利用一级索引查找码值为K的记录 –如果一级索引是稠密索引：同稠密索引查找方法 –如果一级索引是稀疏索引：同稀疏索引查找方法
chapter 4 11
Question: • Can we build a dense, 2nd level index for a dense index? • 1st level dense/Sparse index 2nd level Sparse index higher level Sparse index
10 20
20 30 30 30 40 45
chapter 4 23
• 查找
–首先找到索引中码值小于或等于K的最后一个 索引项E1 –然后向索引起始方向搜索，直到第一个索引 项或找到一个严格小于K的索引项E2为止 –从E2到E1的索引项（含E2和E1）指向所有可 能包含码为K的记录的数据块。在这些数据块 中顺序查找码为K的记录即可
20 30 30 30
• 查找
–找出具有码值K的第一个索引项，后面紧接着 的为其他的具有码值K的索引项。 –依据这些索引指针可以找到所有具有码值K的 记录
• 缺点
–索引大，可能不能放入内存，从而增加I/O
chapter 4
18
策略二
• 稠密索引。为所有码值为K的记录只设一 个索引项。该索引项的指针指向码值为K 的第一个记录。 • 示例
35
Insertion, sparse index case
– insert record 34
10 30 40 60
10 20
30 34
40 50
• our lucky day! we have free space where we need it!
chapter 4
60
36
Insertion, sparse index case
Indexing & Hashing
//利用索引
value
?
File Block Record
value
chapter 4
3
3.1 顺序文件上的索引
3.1.1 Sequential File