前面一篇文章着重讲述了 B+ 树索引，实际上一些数据库中，树索引除了 B+ 树结构，还有其他的一些比较常见的索引结构。

Various Indexes

在介绍具体的数据结构之前，先来看一下数据库中常见的不同的索引形式。

Cluster Index

cluster index，即聚簇索引，指的是将表中的数据全部按照某个索引的顺序进行排列。

以 PostgreSQL 为例，假如我们在 pg 中随机插入了一些数据，它们完全是无序的，sql 如下：

CREATE TABLE users (
  id int,
  name varchar(255) NOT NULL
);

insert into users (id, name) values 
(2, 'b'),
(4, 'd'),
(3, 'c'),
(1, 'a');

如果我们指定了一个索引，并且执行 cluster 操作，那么表中的数据就会按照该字段进行排序。

在此基础上，进行数据的范围扫描将会非常高效。

需要注意的是，聚簇索引的操作是一次性的，也就是说后续插入的新的数据，将不会依照 cluster index 的顺序进行排列。

Implicit Index

数据库系统在针对 table 中的一些唯一性约束的列时，一般会自动为其创建索引。例如主键，unique 约束，看下面的这个例子：

这其实不难理解，因为只要约定了了唯一性约束，在插入数据的时候就要对这个字段进行唯一校验，如果没有索引的话，就会扫描全表去做这个事情，这种昂贵的操作肯定是需要避免的。

这种情况叫做 implicit index（隐式索引），因为这并不是我们主动创建的索引，而是在声明了某种约束之后，由数据库自动为我们创建。

Partial Index

顾名思义，我们可以在某些情况下不对数据库中的所有数据创建索引，而是只对其中一部分数据创建。

例如上面的查询，如果我们确定只会对 c = 'WuTang' 的数据进行查询，那么可以只对这个条件的数据创建索引，这样索引维护的数据量更小。

下图是 PostgreSQL 中的一个例子：

Covering Index

covering index，即覆盖索引，意思是如果一条查询能够在索引当中获取到所需要的数据，就不用去获取整个 tuple 的数据（一般叫做回表）。

例如上面的这个例子，在 a 和 b 列上创建了索引，而查询是根据 a 返回 b 列的数据，此时索引上已经满足查询的需求了，可以直接返回。

Index Include Columns

有一种索引中包含某一列的用法，它会将 include 的列存储在索引中，当查询时，如果需要 select 的列数据就在索引中，那么可以不用去加载整个 tuple 的数据，提高查询性能。

Functinal/Expression Index

这表示的是一种特殊的函数表达式索引，当我们的查询条件包含一些表达式操作，或者函数时，在创建索引的时候就可以对表达式/函数操作。

以 PostgreSQL 为例，下面是一个建表语句和填充数据的 sql：

postgres=# create table users (id serial primary key, login timestamp not null);
CREATE TABLE
postgres=# insert into users(login) select * from generate_series('2018-01-01'::timestamp, now()::timestamp, '1 minute'::interval);
INSERT 0 2481969

查询的 sql 是 explain select avg(id) from users where extract(dow from login) = 2; 在没有索引的情况下，需要进行全表扫描，如果为函数表达式加上了索引，则会走索引扫描，如下图：

Trie Index

前面介绍了几种常见的索引形式，接下来在看来看下另一种常用的树结构索引，Trie 字典树。

Trie 是一种特殊的树结构，与 B+ 树不同的是，B+ 树中每个节点都会存储完整的 key，而 trie 则会根据 key 的相同前缀来构建树结构，如下图是一个 Trie 结构：

三个 key 他们有部分前缀是相同的，因此在 Trie 中只存一次，当需要查找某个 key 时，则从根节点往下，依次比较 key 的每个字符，因此 Trie 又叫做前缀树。

Trie 的特征是每次查找都只会遍历 key 的长度的字符，因此其时间复杂度是稳定的 O(k)，k 是字符串的长度，并且 Trie 没有 B+ 树当中的平衡操作，即节点的分裂和合并。

Leetcode 上有一个实现简单 Trie 树的题目，难度为 medium，可以手动实现下： https://leetcode.cn/problems/implement-trie-prefix-tree/

Radix Tree

Radix Tree，即基数树，实际上是一种对 Trie 树的优化，如果子节点是其父节点的唯一一个节点的话，那么它会和父节点进行合并，进而达到压缩的目的。

具体细节可参考这篇文章：https://blog.ihypo.net/16506944639091.html

Conclusion

这一节主要讲述了不同的索引形式，帮助大家在索引的使用上有更多的了解。

同时也拓展了两种常用于构建索引的树结构，字典树和基数树，可以当做延升内容进行学习。

下一节会继续讲索引，来看看索引并发安全相关的内容。