Index 是 database 里常见的优化手段，用来提升 data retrieval 的速度。Index 通过增加 storage overhead 和写入成本（写入数据的同时也要更新 index），换取更快的读取。Index 让我们无需扫描整张表就能定位数据。Index 可以基于一个或多个 columns 创建，支持快速 random lookup 以及对有序数据的高效访问。

可以把 index 理解为“目录”，指向真实数据的位置。创建 table 某个 column 的 index 时，会在 index 里保存该 column 的值以及指向整行的指针。Index 还能为同一数据提供不同视图：在大数据集里，可以通过 index 定义不同过滤或排序方式，而不需要复制多份数据。

Database index 有两种常见特性：dense 和 sparse，它们各有 trade-off：