数据库索引

索引

• 索引概述

  许多查询只涉及文件中的少量记录，而如果读取整个表的记录，则这种操作方式是低效的。更理想的情况是数据库能直接定位某项记录。为了允许这种的访问方式，设计了与文件相关联的索引。

• 2种基本索引类型

  • 顺序索引
    基于值的顺序排序

  • 散列索引
    基于将值平均分布到若干散列桶中，一个值所属的散列桶是由一个函数决定的，该函数我们称之为散列函数。

顺序文件组织和顺序索引

顺序索引按顺序存储搜索码的值，并将每一个搜索码与包含该搜索码的记录关联起来。
一个文件（专指数据库文件）可以有多个索引，分别基于不同的搜索码。
如果包含记录的某个文件按照某个搜索码指定的顺序排列，那么该搜索码对应的索引称为聚集索引(主索引)
文件不是按照某个搜索码排列的，那这个搜索码对应的索引称为非聚集索引(辅索引)
索引项或索引记录由一个搜索码值和指向具有该搜索码值得一条或多条记录的指针构成。其中又分为稠密索引和稀疏索引。

• 稠密索引
  记录中每一个搜索码值都有一个索引项。

  
  顺序文件上的稠密索引.png

• 稀疏索引
  只为搜索码的某些值简历索引项，因此只有当关系按照搜索码顺序排列时才能用稀疏索引。

  
  顺序文件上稀疏索引.png

利用稠密索引通常可以比稀疏索引更快地定位一条记录。
但是稀疏索引相比于稠密索引占据的空间更小，并且插入和删除更容易维护。
必须在时间和空间上有所权衡。通常为每一个块建立一个稀疏索引是比较好的折中，因为处理数据库的开销主要由把块从磁盘读到主存中的时间决定。一旦将块放入主存中，扫描整个块的时间可以忽略的。

• 多级索引
  索引文件可能占据多个存储块，即便我们能定位索引存储块，并且能使用二分查找法找到我们需要的索引项，我们仍可能需要执行多次I/O操作才能得到我们所需的记录。通过在索引上再建索引，我们能够使第一级索引的使用更有效。

  增加一个二级稀疏索引.png

  按照同样的想法，我们可以在二级索引的基础上建立三级索引。不过，这样也会耗费更多的空间，更好的是采用后面要介绍的B-树。

• 辅助索引

B-树

虽然一级索引或两级索引通常有助于加快查询，但在商用系统中常用一种更通用的结构，这一通用结构称为B-树，最常用使用的是其称为B+树的变体。
【1】B-树能自动保持与数据文件大小相适应的索引层次
【2】对所使用的存储块空间进行管理，使每个块的充满程度在半满和全满之间。

• B-树的结构
  B-树是平衡的，通常B-树有三层：根，中间层和叶，但也可以有任意多层。

B-树.png

• B-树在索引上的应用
  B-树是用来建立索引的一种强有力的工具。下面是一些实例：

  • B-树的查找键是数据文件的主键，且索引是稠密的。
  • 数据文件按主键排序，且B+树是稀疏索引，在叶结点中为数据文件的每个块设有一个键-指针。

• B-树的效率
  假设一个数据库一个存储块有4096个字节，整数型键值4字节，指针8字节，则4n+8(n+1)<4096，则n最大可以为340，假若一般块充满渡介于最大和最小中间，即一般块有255个指针。一个根结点有255个子结点，有255^2= 65025个叶结点，在这些叶结点中，我们可以有255^3，即约1.668 × 10^3万个指向记录的指针。亦即记录数小于等于1.668 × 10^3万的文件都可以被3层的B-树容纳。

散列文件组织和散列索引

顺序文件组织的一个缺点就是我们必须访问索引结构来定位数据，或者必须使用二分法搜索。这会导致过多IO操作。
我们用桶来表示能存储一条或多条记录额度存储单位，通常一个桶就是一个磁盘快。

• 散列函数
  用K表示所有搜索码的集合，用B表示所有桶地址的集合。函数是一个从K到B的映射函数，Bi = h(Ki);
  散列函数具有下面2个假定：
  • 分布式均匀的。
  • 分布式随机的。
• 桶溢出处理
  • 桶不足
    用N > n / f。N表示桶数目，n表示记录数目，f表示桶能存放的记录数目。
  • 桶偏斜
    某些桶分配的记录数比其他的多，原因有多条记录有相同的搜索码，或者散列函数设计不好。