Index 是数据库为了加速检索，提高系统性能而引入的一种数据结构，根据内存空间的利用率及内存任务划分的不同，Index 可能存于内存或是磁盘中。然而，我们好奇的是：

  • Index 对于 Database 来说有什么作用，是不可或缺的吗？
  • Index 是一种什么样或一些什么样的数据结构？不同的数据结构的动机和目的是什么？各有何优劣？
  • Database 在什么情形下应当建立 Index？ Index 的代价有哪些？

接下来，我们就开始一步步展开，回答以上几个问题。说到 Index 对数据库的作用，不如先设想一个原始的场景：一个数据库没有索引，是如何运作的？

如果没有 Index …

打个比方，如果我的数据库有一个 Table 存的是办公室的职员名单，那么一个典型的 query 语句如下所示：

SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’

没有索引的情况下，数据库要返回姓名为 Jesus 的职员信息，就必须顺序查找所有的表项（不能再第一个匹配结果后停止，因为可能有多个名为 Jesus 的职员），这样一来，当表中的数据量很大时，一次 full scan 的时间损耗就会很高（其时间复杂度为O(N)）。

那么，有没有一个能够辅助检索的工具呢？对了， Index 就是这样一个有用的工具。

Index 是什么

Index 本身也是存储在内存或者磁盘中的数据结构，它类似于 Table 里的一个表项，只不过是以键值对(key-value)的形式存储的。”key” 就是 Table 中某一列的名称，比如 Name, Sex, Age, Occupation 等都可以作为 Index 的键，而 Index 的值则不是某一列或某几列的内容，而是该键所在的 Tuple 的地址信息（内存地址或磁盘地址）。这样做的理由是：

  • 如果要检索对应某个键的好几个元素信息，则单列作为键值对的值是不能满足要求的；
  • 如果要存储好几列的元素信息作为值，则相当于重新制作了一个 Table，占用空间太大，而内存资源则非常有限。

因此，使用地址指针作为值，既能够满足找到对应某个键的整个 Tuple 信息（通过指针找到该行），又能有效地节省空间，一举两得。

那么，既然是作为键值对的形式， Index 的数据结构有哪些选择呢？

Index 的数据结构

为了提高检索速度，一般来说 Index 都不会做成随机的顺序检索的形式。最广泛使用的 Index 数据结构时 B 数及其变种（B+ 树），B 树是一种有序的数据结构。比如在以字符串为键组织 Index 时可以按字母顺序来排，以阿拉伯数字为键组织 Index 时可以按数的大小顺序来排。这样一来，就可以通过二分查找法很快地定位某个键所在的地址了（时间复杂度O(logN)）。

另外一种比较容易想到的是哈希表。哈希表的单个数据检索速度非常快，时间复杂度是O(1)，这是因为哈希表组织的键值对形式是 value = hash(key)。通过一个键的内容查找到地址值只需要一次哈希映射，而不需要顺序或者是二分的方式进行查找。

许多研究者也对 Index 数据结构进行了针对性的优化设计工作，比如 R 树, T 树，混合 Index 设计等。

不同的 Index 数据结构的选择必须要结合实际的数据库环境及工作环境，比如数据库表项的大小，工作负载的特征模式，内存大小等。

以哈希 Index 为例，虽然它的单个数据检索速度非常快，却没办法处理 Range Query 的情形。比如我要找出职员数据库中所有年龄大于 30 岁的职员信息，哈希表就无能为力了。而 B 树则可以通过年龄这个键，仍能以 O(logN) 的时间复杂度找到所有匹配结果。

Index 的缺点

当然，Index 也并不是完美的。虽然它的产生是为了帮助数据库更快地进行数据检索，但是它仍有两个无法规避的缺点：

  • 第一，Index 不可避免地占用了有限的内存空间，尤其在关系型数据库中，要以不同的列为键建立索引，空间消耗极高，挤占了本可以存放表数据的空间；
  • 第二，Index 并不保证能够提升检索的速度。比如对于 Selectivity Ratio 较低的键（比如男女性别，二分法），通过 Index 索引可能不如一次 full table scan。

Index 如何帮助数据库

但归根结底，在大部分情况下， Index 对数据库操作而言都是有增益作用的，这一点已经经过了科研和实践的检验。而关于何时使用 Index 何时不用 Index 的问题，则是数据库中长久以来的一个研究问题。

一般来说，当我们创建一个 Table 时，如果指定了 PRIMARY KEY，那么就会基于这个列建立一个一级 Index，如果恰好这个 KEY 是 UNIQUE 的，那么选择为它建立哈希Index也许就非常合适了。另外，根据不同数据库的自身机制设计，何时建立 Index 以及决定某次响应操作是否要查询 Index 就取决于它自身设计的一套算法了。比如基于访问模式的 Index 建立机制以及基于 Selectivity Value 的 Index 选择机制等。