数据库学习笔记(06): Indexing and Hashing

喂喂士武

• Search key：一个关系中一个或多个属性，常用于查找文件中的数据记录
  
• Index文件：一个特殊的文件，由一些记录构成，称作索引项（index entries），两个部分：search key和pointer，pointer指向数据文件中search key对应的数据记录
  
• 顺序索引：基于记录中某个属性值的顺序建立的索引，比如成绩顺序
  
• hash索引：根据记录的查找键的值，使用一个函数计算得到的函数值作为磁盘块的地址，对记录进行存储和访问，通常用桶作为基本的存储单位，一个桶可以存放多个记录
  
• 评估：
  
  
  
  • 查找具有特定值的记录还是查找属性值在一定范围的记录
    
  • 访问时间：查询时找到数据项或数据项集合的时间
    
  • 修改时间：在数据文件中增加或删除数据的时间，以及更新索引（插入索引项和删除索引项）的时间
    
  • 空间开销：索引文件占用的存储空间
    
  
  

Indexes on Sequential Files

顺序索引：索引项根据search key排好序，索引文件中的索引记录都是按照search key排好序的。

• 对于数据文件，可以按照某个属性的值排好序存放在文件中，主索引（聚集索引）指的是索引项中的search key是数据文件中排序的属性，而且顺序与数据文件一致
  
• 当数据文件中的记录顺序与索引文件中索引项的顺序不一致时，这个索引是辅助索引（非聚集索引）
  

Dense Index Files

• 稠密索引：索引文件中search key所有取值都出现在索引文件中
  

Sparse Index Files

• 稀疏索引：索引项中只包含search key的部分取值
  
• 要查找搜索键值为 K 的记录，我们： 查找搜索键值最大< K 的索引记录，按顺序从索引记录指向的记录开始搜索文件
  

Dense vs. Sparse

• 稀疏索引的空间开销比稠密索引小，定位数据比稠密索引慢
  
• 将两种索引结合起来形成多级索引。首先为顺序文件的每一块建立一个索引记录，得到一个以块为基本单位的稠密索引，然后再在稠密索引的基础上建立一个稀疏索引。查找时，首先在稀疏索引中确定记录在哪一块，最后在数据文件的块中顺序查找，找到所在的记录
  

Multilevel Index

• 如果索引文件小到可以放入内存，搜索一个索引项的时间会很短。但是索引文件很大不能放在内存中时，需要从磁盘调用索引文件的数据块，开销变大
  
• 方法1：索引文件是按照索引项排好序的，那么用二分查找算法来定位索引项可以吗？如果有了溢出块就不能用二分查找了？
  
• 方法2：建立多级索引：内层索引是主索引，外层索引是主索引之上的稀疏索引，为索引文件建立索引。如果有数据更新时，所有层的索引都要更新。
  

Secondary/Nonclustered Index

• 辅助索引和主索引的目的一样，但是索引文件中search key的顺序与数据文件的顺序不一样
  

• 如果主索引的search key 不是candidate key ，索引指向具有该特定 search key的第一条记录，其他记录都连续存放，顺序扫描得到。 如果辅助索引的search key不是candidate key，具有该特定search key的记录不是连续存放，散布在文件的任何地方，辅助索引的索引项必须包含指向第一个记录的指针。索引记录指向一个存储桶，该存储桶包含指向具有该特定搜索键值的所有实际记录的指针。
  

• 如果索引是主索引，顺序扫描可以高效地完成数据更新；但是如果是辅助索引，那么代价很高，因为会访问不同的数据块来完成数据的更新，有可能增加新的数据块。磁盘访问时间增大。
  

B+ Tree Index Files

• 索引顺序文件的缺陷：随着文件的增大，溢出块不断产生，为了保持顺序，文件需要阶段性地重组，导致索引查找性能和数据顺序扫描的性能都会下降
  
• B+树是一种最广泛使用的索引文件结构之一，采用平衡树结构，是在数据插入和删除的情况下仍能保持执行效率的结构，只需很小的、局部的变化自动重组文件。针对更新频繁的文件，减少了文件重组的代价
  
• B+树的缺点：会有插入数据和删除数据的额外开销，增加空间开销
  
• B+树：
  
  
  
  • 树中非根、非叶子节点有 \lceil n/2 \rceil ~ n 个孩子
    
  • 叶子节点有 \lceil (n-1)/2 \rceil ~ (n-1) 个值
    
  • 特殊情况：
    
    
    
    • 如果根不是叶子，则至少有2个孩子
      
    • 如果根是叶子，则根节点存储0 ~ n-1个值
      
    
    
  • 例如n=4
    
  
  

• 叶子节点：若search-key不是数据文件的主键，且search-key值的顺序也不是数据文件的顺序（数据文件按照另外的属性值排序），则指向一个桶，桶中的记录具有search-key的值
  
• P1指向的子树的所有search-keys值小于K1，Pn指向的子树的所有search-keys值大于等于Kn–1，Pi指向的子树的所有search-keys值大于等于Ki–1且小于Ki
  

• B+树查询：
  
  
  
  • 根结点中找>K的最小查找键值
    
  • 如果存在这样的值， 设为 K_i 然后沿着Ki左边的指针 P_i 到达第二层的结点；
    
  • 如果不存在这样的结点 （ k \geq K_n–1） ，沿着指针 P_n 到达第二层的结点
    
  • 直到叶子结点，找到一个指针直接指向数据文件的记录，或指向一个桶。
    
  
  

• 假设有k个search key，树的高度不超过 \lceil log_{\lceil n/2 \rceil}(K) \rceil ，即从跟节点到叶子结点的遍历长度
  

• 插入：
  
  
  
  • 分裂时，把n个 (search-key value, pointer) 对按顺序放在两个结点中，前 \lceil n/2 \rceil 个value放在原来的结点中，余下的放在新的结点中。
    
  • 在父结点中插入新结点中的最小查找键值
    
  • 如果父结点满了，那么分裂父结点，再在上一层结点中加入一个新的查找键值
    
  
  

• 删除：
  
• 字符串上的索引：前缀压缩
  
  
  
  • Silberschatz只用在非叶子节点存储Slib就行
    
  
  

Hash Index

• An ideal hash function is uniform（均匀的）：每个桶内分配的查找键值数目大体相同。
  
• Ideal hash function is random（随机的）：Hash函数值不受查找键各种顺序的影响
  
• 每个桶的空间是固定的，如果桶已装满记录，那么插入新记录时，桶溢出。原因在于：
  
  
  
  • 桶的数量少
    
  • 记录分布不均匀
    
  
  
• 如果一条记录必须插入到桶b中，如果桶b已满，系统会为桶b提供一个溢出桶，如果溢出桶也满了，会继续提供另一个溢出桶。一个给定的溢出桶用链表链接起来，这种处理称为溢出链
  

查询时除了查询桶b中的数据，还需要检查桶b的溢出桶中的记录

• Hash索引将search-key值及其相应的指针组成hash文件结构，将hash函数作用于search-key来确定对应的桶，然后将这个search-key值已经相应的指针存入桶中（或溢出链中）
  
  
  
  • 严格地说，hash索引是辅助索引。如果文件本身是hash结构，建立一个hash主索引就没必要了
    
  
  

在instructor ID上建立索引。蓝色框是数据记录所在的数据块。Hash索引文件一共有8个桶，每个桶存储的search-key（ID）。可以看到桶5有溢出桶。

Bitmap Indices

位图索引对于查询多个属性非常有用，对于单个属性查询不是特别有用


用于集合枚举比较方便
Index Selection

在建立索引、维护索引与加速查询之间进行权衡

• 如果应用是查询密集型的，就在针对频繁查询的属性上建立索引；
  
• 如果应用是修改密集型的，如经常需要对数据进行增删改操作，慎重考虑索引的构建；
  
• 如果数据集较小，不必用索引了
  

上篇：数据库学习笔记(05): Storage and File Structure
下篇：数据库学习笔记(07): Query Processing