索引以一个或多个字段的值为输入并能“快速地”找出具有该值得结果。建立索引的字段称为查找键。在本篇文章中先来看看索引的基本概念，并看几种索引数据结构表示。

一、索引结构基础

一个数据文件可以拥有一个或者多个索引文件，每个索引文件建立查找键和数据记录之间的关联，查找键的指针指向与查找键具有相同属性值的记录。

通常我们在关系的主键上建立主索引，在其他的属性上建立辅助索引。

Ⅰ、顺序文件

顺序文件是对关系中的元组按 主键 进行排序而生成的文件。关系中的元组按照这个顺序分布在多个数据块中。

上图右边部分显示了一个顺序文件，每个存储块中只可存放两条记录。顺序文件一定是排好序的 。

Ⅱ、稠密索引

如果记录是排序好的，那么我们就可以在记录上建立稠密索引。我们依然上图，现在是左边部分。稠密索引是一个存储块，块中的内容为：

记录的键，以及指向记录本身的指针。

比如上图中的“10、20、30”等等都是记录的键。而指向记录的指针的表示方式为： 磁盘号 -> 磁盘内的柱面号 -> 柱面内的磁道号 -> 磁块号 。

稠密索引文件中的索引块键的顺序 与 文件中的排序顺序一致。因此我们就可以通过索引文件的键找到对应记录的指针，并顺利地找到对应的记录。

Ⅲ、稀疏索引

稀疏索引只为数据文件的的 每个存储块设一个键-指针对 。相对于稠密索引来说的确是节省了存储空间，但是对于查找给定值则需要更多地时间。

可以看出在索引文件的存储块上，键10、30、50、70和90分别指向数据文件的每一个存储块。而不是指向的数据文件中的每一个记录。

Ⅳ、多级索引

多级索引也就是我们可以为索引文件再建立索引。

一级索引可以是稀疏索引或者稠密索引，但是 二级或者更高级的索引必须是稀疏索引。

如果二级索引也就是稠密索引的话，那么所需的空间和一级索引所需的空间一样，就无法达到节省存储空间的目的。

Ⅴ、辅助索引

辅助索引是相对于主索引而言的，和前面提到的稠密索引、稀疏索引划分的维度不一样。在主键上的索引称为主索引，而在其他属性上的索引称为辅助索引。

辅助索引和主索引最大的区别是辅助索引不决定数据文件中记录的存放位置，仅仅只能知道记录当前存放的位置。

辅助索引总是稠密索引！！！

这是因为辅助索引不影响记录的存储位置（也就不是前面提到的顺序数据文件），因此我们就不能根据它来预测键值不在索引中显式指定的任何记录的位置。

  • 1、 数据文件中的数据是无序的；
  • 2、 索引文件中的键是有序的；

如上图，在辅助索引中，我们为了检索键20对应的数据，我们不仅仅要查找两个索引文件块，而且我们还要根据数据文件指针访问3个不同的数据文件块。因此：

查找同样数量的记录，使用辅助索引可能要比使用主索引花费多得多的磁盘IO 。

辅助索引还用作某些数据结构的主键索引，这些 结构有：

  • 1、 堆 （heap）：关系的记录之间没有特定的顺序；

  • 2、 聚集文件：假设关系R和关系S（这里的关系可以理解数据库表），R中的元组和S中的元组具有多对一的对应关系。一种组织结构是把关系R的每个元组和关系S中的元组存在一起；

    例子：存在两个关系（表）：

1
2
Movie(title, year, length, genre, studioName, producerC#);
Studio(name, address, presC#);

现在我们有一个查询的SQL:

1
2
3
SELECT title, year
FROM Movie, Studio
WHERE presC#=zzz AND Movie.studioName = Studio.name;

这个SQL的意思是已知一个电影制片厂，我们需要找到该制片厂制作的所有电影。因此我们可以根据Studio和Movie建立一个 聚集文件 ：

从这里我们看出关系Movie中的元组放在关系Studio元组一起。这样的话我们就可以用尽量少的I/O找到制片厂的所有电影。尽管如此，在Movie上对任意属性建立的索引只能是辅助索引（即影片的顺序已经不是有序的了）。

Ⅵ、辅助索引中的间接方案

对于上图而言，比如键20出现三次，那么索引文件中就需要写3次。为了解决存储多次键的问题：

可以增加一个 桶 的 中间层！！！

它介于辅助索引文件和数据文件之间。

在索引文件中每个查找键有一个“键-指针对”，指针指向一个桶文件。比如上图对于索引文件中的键20，它的指针指向桶文件中的第三个位置处，在此之后的三个桶均为键20对应的数据文件指针。

从这儿看这一张图和上一张并没有省略空间，而且在原有索引文件键的基础上还增加了桶文件。然而对于 查找键值的存储空间比指针大（也就是指向桶的指针），并且每个键平均至少出现两次时，使用桶间接文件就可以节省空间。

除此之外，我们还可以在不访问数据文件记录的前提下，利用桶的指针来查询具有多个条件的场景。

当每个条件都有一个可用的辅助索引时，我们可以通过在主存中通过将指针集合求交来找到满足所有条件的指针 。

然后查看交集中的指针，并且通过该指针找到对应的数据记录。

我们来看看下面的SQL语句：

1
2
3
4
/// Movie表（title, year, length, genre, studioName, producerC#）
SELECT title
FROM Movie
WHERE sutdioName = 'Disney' AND year = '2005';

即找到Disney工作室在2005制作的影片，我们通过桶来看看如何进行查询的：

很明显Movie元组的第三条（下标从1开始）记录就是我们通过求交集之后得到的记录。

二、B-树

这里的B-树（B Tree），并不是B减树。而是将横杠理解为破折号，然后读作“B树”。以及其变体B+树（B Plus Tree）读作“B加树”，除非特别说明在下文中的B-树都指的是B+树。

  • B+树能自动地保存与数据文件大小相适应的索引层次;
  • 对所使用的存储块空间进行管理,使得每个块的充满程度在半满和全满之间;

B-树把它的存储块组织成一颗平衡的树，即从树根到树叶的所有路径都一样长。每个存储块存放n个查找键和n+1个指针。

  • 1、叶结点中的键是数据文件中键的拷贝。并且它们是 排好序的 ，从左到右分布在叶结点中；
  • 2、根结点至少有两个指针被使用；
  • 3、 叶结点中最后一个指针指向它右边的下一个叶结点存储块 （上图红色域和红色箭头）；
  • 4、在内层结点中，所有的指针都可以用来指向B-树下一层的块。而不是实际的数据文件存储块；
  • 5、无论是内层结点还是叶子结点，其真正使用的指针至少有 (n+1)/2 个（n指的是查找键的个数，n+1指的是结点指针最多的个数）；

因此B-树可以作为一种建立索引的数据结构，它的叶结点为数据文件每一个记录设有键-指针对。或者该数据文件可以按照主键排序,也可以不按主键排序:

  • 数据文件按主键排序,并且B+树是稀疏索引。在叶结点中为数据文件的 每个块 设有一个键-指针对；
  • 数据文件按非主键属性排序，且该属性是B+树的查找键。叶结点为数据文件里出现的每个属性（比如Studio表的name属性）值设有键-指针对，其中指针指向该属性已排序记录的第一个。

Ⅰ、B-树的查找

我们假设B-树是稠密索引，因此在数据文件中出现的每个查找键都会在叶结点中出现。如果想要找出查找键值为K的记录，我们 从根到叶递归查找，查找的大致过程为：

  • 1、如果我们处于叶结点上，我们就在其键值中查找。若第i个键是K，那么第i个指针可让我们找到所需的记录。
  • 2、如果我们处于内部结点，那么我们就需要根据B-树的性质找到对应的子节点，一直递归到叶子结点；

B-树不仅仅对上面提到的单个键查找有用，而且还可以对查找键值在某个范围内的查询。比如：

1
2
3
SELECT * 
FROM R
WHERE R.k >= 10 AND R.k <= 25;

首先找到范围查找的下界对应的叶子结点，然后在叶子结点中查找大于下界并且小于上界的叶子结点，最后可以根据叶子结点获取到对应的指针（可以是数据文件记录，也可能是桶）。

需要注意的是：

在查找大于下界的叶子结点过程中，是通过 链（也就是上图中的红色指针）直接找到下一个叶子结点。

Ⅱ、B-树的插入

对于B树的插入主要从传统的B树，以及应用于数据库索引的B+树。

1）、B树插入

当插入一个键时，我们实行从上到下插入：

  • 如果叶子结点未满，则直接插入到对应位置；
  • 如果根结点已满，则直接分裂根结点。并使得树整体长高；
  • 从上到下依次按照指定路径，发现满结点则就行分裂，并将其提向父结点；

这是自顶向下的插入方式，和2-3树等数据结构的插入类似，可以查看我另外一篇讲2-3树和红黑树的文章。下面我们来看一个插入的示例，应该就很好理解了。现在我们有一颗树：

现在要向该树插入键5：

2）、B+树插入

B+树在索引文件中使用较多一些。其大致步骤如下：

  • 找到适当的叶结点，如果该叶结点有空闲空间的话，我们就把键放到那里；
  • 如果适当的叶结点没有空间，我们就把该叶结点分裂成两个，并且把其中的键分到这两个新结点中。使得 每个新结点有一半或者刚好超过一半的键 ；
  • 某一层（比如为p）的结点分裂在其上层（比如为q）看来，那么在q看来即有新的结点需要需要插入到本层。这是一个递归的过程；
  • 如果我们试图插入键到根结点中并且根结点没有空间，那我们就分裂根结点成两个结点，并创建一个新的根结点。此时也就是树长高；

现在我们对下面的这颗B+树（4路，满键数量为3）执行插入键42的操作：

找到该叶结点为满结点（键值分别为：31、37、41），现在我们需要对该叶结点进行分裂，并将键42放入合适的位置：

现在就相当于对其父结点（键值为23、31、43）执行插入操作。但是其父结点依然是满结点，因此我们也需要对其父结点进行分裂。现在需要明确插入到父结点（23、31、43）结点的键是多少。

先别急，回过头看看原B树。父结点（23、31、43）的键值是不是它子节点（23、29），子节点（31、37、41），子节点（43、47）中最小键值？那好办了，我们看待插入子节点（41、42）的最小键值为41.因此待插入父结点的键为41。

因此将41分裂出来，其左子节点为(23、31)，右子节点为（43）。但是结点（23、31、43）已经是满结点了，如果此时插入41之后就变成了 （23、31、41、43），很显然这不是满足，因此需要将该结点分裂两个新结点。这里明显需要将键41合并到根节点。最终的B+树如下所示：

B树/B+树删除

分为B树的删除和B+树的删除。但是删除操作相对于插入操作来说的确是要复杂不少。

1）、B树的删除

首先我们来看看B树的删除，我这里借鉴《算法导论》中的删除方法。由于删除一个关键字可以从叶结点，也可以从内部结点删除。如果我们从内部结点删除一个关键字时，还需要重新安排这个结点的孩子。必须保证一个结点不会在删除期间变得太小，但是：

根节点允许有比最少关键字数还少的关键字个数。

以 x为根 的子树中删除关键字k（一定要记住是以x为根的子树）。x中关键字的个数至少为最小度数t（t >= 2）。如果根节点x成为一个不含任何关键字的内部结点，那么x就要被删除，x的孩子结点需要成为新的树根，并且树的高度减1。

下面是删除的详细规则：

  • 1、如果关键字k在结点x中，并且x为叶结点，则从x中删除k；

  • 2、如果关键字k在结点x中，并且x为内部结点：

    • 如果结点x中 前于 k的子节点y至少包含t（最小度数，比如2）个关键字，则找出以y为根的子树中的 前驱k’ ，递归地删除k’，并在结点x中用k’代替k；

    • 对称地，如果y少于t（最小度数，比如2）个关键字，则检查结点x中 后于 k的子节点z。如果z至少有t个关键字，则找出以z为根的子树中的 后继k’。递归地删除k’，并在x中用k’替换k；

    • 如果结点y和z都少于t个关键字，则将k和z合并进y。然后释放z并递归地从y中删除k；

  • 3、对于 内部结点x，关键字k并不在结点x中（k可能在其他内部结点，也可能在叶子结点），则确定必包含k的子树的根 $x.c_{i}$ 中。如果 $x.c_{i}$ 关键字个数少t，则用如下步骤来保证下降到至少包含t个关键字的结点。然后通过对x的某个合适的子结点进行递归而结束。下面是下降的方案：

    • 如果 $x.c_{i}$ 关键字个数少于t个，但是它相邻兄弟结点至少包含t个关键字：则将x的某一个关键字降至$x.c_{i}$中，将$x.c_{i}$相邻左兄弟或者右兄弟的一个关键字升至x。

    • 如果 $x.c_{i}$ 和它左右兄弟结点的关键字个数都是少于t的，则将 $x.c_{i}$ 与其中一个兄弟合并。即将x的一个关键字移动到新合并的结点，使得其成为该结点的中间关键字。

需要注意的是：

这个方法是 自顶向下 的 ！！！

2)、B+树的删除

我们在看完了B树的删除之后，再来看看B+树的删除。如果我们要删除一个具有给定关键字k的结点，我们必须要先定位该记录和它在B+树 叶结点 中的键指针对。

注意：这里是删除叶结点包含关键字k的结点。

这是因为B+树的内部结点不存储索引信息，它只是表明当前结点能够到达叶结点的最小值。

首先如果发生删除的B+树结点在删除后至少还有t个（最小数量）的关键字，那就不需要再做其他事。但是当删除之前B+树的某一结点关键字数量刚好是t个，那么在删除之后就不满足B+树的约束条件。这时：

  • 1、如果与结点x相邻的兄弟结点y中有一个 超过 了t（最小数量）个关键字，那么可以将y结点的关键字移动到结点x中。此时需要更新结点x和结点y的父节点，使其能够表示可以访问到的最小关键字；
  • 2、如果结点x的兄弟结点都没有超过t个关键字的，我们可以将结点x和其中一个结点合并，同样地我们需要调整父结点。 如果父结点符合最小数量的关键字，那么我们就完成了操作；如果不符合最小数量关键字，那么我们需要递归向上执行这个算法。

还是以下面这颗B+树为例：

下面我们来删除关键字7，我们在第二个叶子结点中找到该关键字。下图是删除关键字7的过程(图中右半部分由于和此次删除无关，我就直接用灰色大矩形表示)：

这里第二个叶子结点向其兄弟结点（第一个叶子结点）借用了关键字4，并且更新了它们共同的父结点。

然后我们来删除关键字11，同样地也是在第二个叶子结点。不过这时就没办法向第一个叶子结点借用关键字了，因为第一个叶子结点也没有多余的关键字（这里的t为2，即最少需要两个关键字）。下图展示了删除过程：

现在就可以看作是对于父结点的删除操作，其兄弟结点可以借用的关键字。如下图：

红色的虚线箭头表示关键字的移动方向。

B+树的删除是 自底向上 的 ！！！

3)、B树的效率

如果每个块容纳的关键字数量n相当大的话，分裂或者合并的情况将会很少发生。当分裂和合并必需时，绝大多数的时候都被限定在叶结点。

磁盘I/O数和B树的层数有关：

对于查找而言，磁盘I/O数比树的层数多一；对于插入或者删除而言，磁盘I/O数比树的层数多二；

对于典型的键、指针和块大小来说，三层就足够了。因此当我们把根结点块永久地缓存在主存中时，磁盘I/O的树还要减少一次。

三、散列表

散列表也可以用作索引。有的散列表包含许多的记录，以至于它们主要存放在辅助存储器上。对于存放在辅助存储器上的散列表，每一个桶由存储块组成。

通过散列函数h得到的散列值，这个散列值定位到某个桶。如果桶中有太多的记录，那么可以给该桶加溢出块的链以存放更多的记录 。

前面说的散列函数，该函数的计算规则如下：

  • 1、当键为整数时，散列函数的一种常见选择是计算 K/B 的余数（K表示键值，B表示桶的数量）;
  • 2、当键为字符串时，可以把每个字符看作一个整数，然后把它们累加起来，并将和处于B,然后取余数;

总的来说就是：一个桶可以包含多个存储块，并且每一个桶还有附加块以存放更多记录。而一个存储块（逻辑概念，不是实际存在的）是可以存放多个记录的。

  • 对于散列表的插入，如果根据散列函数得出的桶有空闲空间，则将该记录直接放入桶中；如果对应的桶没有空闲空间，我们则需要增加一个溢出块到该桶的链上，并把新记录存入该块；

  • 对于散列表的删除，大致上是通过散列函数找到对应的桶，并从桶内的存储块或者溢出块删除对应的记录。如果此时有溢出块，并且删除的记录是在桶内的存储块中，删除之后由于桶内存储有多余的空间，我们可以把溢出块的记录移动到存储块中。如果此时溢出块不包含记录，则可以删除溢出块。

从效率上来看，如果有足够多的桶，那么一般的查找只需要一次磁盘I/O就可以了。当文件不断增长，那么桶内就不能存储所有的记录。而记录的查找就转移到了链表，那么在链表中的每一个块都需要一次磁盘I/O。

因此相对于上面的静态散列，下面我们来看看两种动态散列：可扩展散列、线性散列；

可扩展散列

它在简单地静态散列基础上增加了：

  • 1、 为桶引入了一个中间层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶；
  • 2、 指针数组能增长，它的长度总是2的幂；
  • 3、 桶可以共享数据块：并没有每个桶都有一个数据块，如果某些桶中的所有记录可以存放在一个块中，那么该数据库就被多个桶共享；
  • 4、 散列函数为每个键计算K位二进制序列，其中K足够大。桶的数目总是使用从序列第一位或最后一位算起的中的i位，这个i小于K。也就是说桶的数量为 个；

下图为一个可扩展散列表。

图中的信息很好理解，我主要来说一下数据块右边的附加信息 “2” 所表述的含义。这里的数字2是表示位序列中有2位用来确定记录在该数据块中的资格。

怎么来理解这句话呢？上面我们提到了桶是可以共享数据块的，也就是说如果存在两个桶共享同一个数据块，我们就需要通过位序列中指定位数的数据来得到当前记录归宿于哪个桶。

比如上图中的第三个数据块，两个桶指向的同一个数据块，通过附件信息的数字2，我们可以观察位序列前面两个二进制位，从而知道第一个记录和第二个记录分别属于桶2和桶3。

插入操作

根据桶数组中的某一项的指针找到对应的存储块，如果存储块未满，则将新记录放入存储块中；如果该存储块空间已满那么此时就需要分裂存储块，具体分裂方法如下：

假设 j 表示散列值中用于确定存储块的资格（也就是上图右边小方块的数字用j来表示），而 i 表示桶序号的位数 （比如上图中的 i = 2）：

  • 1、当 j < i ：我们需要使用下面的方法来执行插入操作。但是下面的分裂有可能根本不能解决问题，即有可能将原存储块中的所有记录都分配到新存储块中。 因此 我们需要对仍然太慢的块用下一个更大的j重复下面的过程：

    • a）、将该存储块分裂成两个存储块；
    • b）、根据记录散列值的第 j + 1 位来对原存储块中的记录分离：即当散列值的第j+1位为0时，将该记录放入原存储块中。当散列值的第j+1位为1时，将该记录放入新的存储块中；
    • c）、将上图中小方块的数值 由j更新为j+1 ；
    • d）、调整桶数组中的指针，同样根据第 j+1 位的数值来决定桶数组中的指针是指向原存储块，还是新存储块；

  • 2、当 j = i：我们必须先将i+1，这使得桶数组的长度翻倍，因此就会存在两个桶指向了同一个数据块。而此时加1之后的i是大于j的，也就是说现在也满足了条件1。因此我们就可以使用第一条的方案来进行插入操作；

可扩展散列的问题也很明显，当桶数组翻倍时要做大量的工作；而且由于桶数量增多会导致内存中的桶需要放入磁盘中，而增加了磁盘I/O的次数；最大的问题是散列值的前i位可能相同，但是该数据库并未装满。这是一个极大的浪费。

线性散列

线性散列表的桶增长速度相对与可扩展散列增长来说相对要缓慢一些。

假定散列函数值的 i 位用来给桶数组项目编号（桶数组项的下标，即这个下标由i位二进制表示），比如这里i为4，对于数组下标为6的二进制序列为0110。

下面是线性散列表的特点：

  • 桶的数目和记录的总数比值不能太大；
  • 允许有溢出块；
  • 散列函数得到的位序列从 右端（低位） 开始取；

插入操作

这里我们假设桶数组包含的桶总数为 n 。此时有一个键值为K的记录想要插入到编号为 m 的桶中，这里 m 为数组下标，其二进制序列表示为 $b_{1}b_{2}…b_{i}$，比如 1101 之类的。如果：

  • 1、$m < n$：那么将新纪录放入放入编号为m的桶中；
  • 2、$n \leqslant m \leqslant 2^{i}$：即桶m还不存在，因此我们需要创建桶，并把记录存入下标为 $m - 2^{i - 1}$的桶中；
  • 3、如果桶中没有空间，那么我们创建溢出块，并把它链接到该桶上。而记录就存入该溢出块中；

每次插入时，我们都看当前的记录总数占桶总数的比例。如果该比值太大，我们就增加下一个桶到线性散列表中。而记录的划分则是从散列函数的低位开始对比。

四、后续

本篇文章主要是了解了索引的概念。索引的类型（稠密索引、稀疏索引，辅助索引是稠密索引）。以及表示索引的数据结构（B+树、散列表扥等等）。在下篇文章我们将会看一下多维索引，以及位图索引。