Indexes

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：

Dense Index

Dense index 为 table 的每一行都建立 index 记录。每条 index 记录包含 search key 和指向实际记录的指针。

Dense index 在写入时维护成本更高：每行都需要 entry，insert/update/delete 都要更新 index，占用更多 memory。好处是可以用 binary search 快速定位，并且不要求数据有序。

Sparse Index

Sparse index 只为部分记录建立 index 记录。

Sparse index 写入维护成本低，因为只包含部分值，insert/update/delete 更快，占用内存更少。但查找数据会慢一些：通常是先 binary search，再顺序扫描定位。Sparse index 也适用于有序数据。