Btree索引

为了加快点查速度，数据库系统需要引入索引，尤其是在 OLTP 场景下。

基础

如果粗略分类，常见的索引组织形式可以看作 Hash 和 Tree 两大类。PG 诞生于内存紧张、磁盘 I/O 是主要瓶颈的年代，因此面向磁盘访问模式优化的 B-Tree 自然成了最重要的选择。

              [ Root ]
                 |
        +--------+--------+        root often stays hot in cache
        |                 |             
   [ Internal ]      [ Internal ]       read each [node] from disk
        |                 |
   +----+----+        +----+----+       until leaf    
   |         |        |         |
 [Leaf]<->[Leaf] <-> [Leaf]<->[Leaf]

其内部实现可以参考我之前为 GP 社区写的一篇文章：GP 中的 B-Tree 实现。其中介绍的实现与 pg9.6 基本一致。

再补充记录几个要点：

通过 opclass / opfamily 支持多数据类型，有点类似 C++ 里的 traits。
与表数据一样，索引页的变更也需要 WAL 支持。
索引项本身并不保存完整的 MVCC 可见性信息，因此可见性判断仍以 heap tuple 为准；而像 HOT 这样的优化，则是建立在“某次 update 不需要新增索引项”这一前提之上的。
索引操作还要考虑高性能并发控制，例如 B-link tree。PostgreSQL 的实现可以参考这篇文章。
索引键如何删除、何时真正回收空间，也值得结合上面的资料一起看。

在最近几个大版本（12~18）中，PG 对 B-Tree 做了不少改进，但整体结构和核心操作并没有本质变化，主要包括：

性能和空间优化：并行索引创建（CIC）、索引键 deduplication、bottom-up deletion、异步 I/O 支持等。
优化器适配：覆盖更多查询场景，比如 IN (...)。
运维可观测性：监控索引创建进度、提供更多 EXPLAIN 信息等。

Discussion

B-Tree 索引主要服务于 OLTP 场景；而在 OLAP 场景中，更常见的是 BRIN、bitmap index（GP 独有）等其他索引形式。

和 PG 的 heap + btree 相比，另一类常见的数据组织方式是 LSM。《DDIA》中有一节专门比较了它们，重点就在读写放大上的差异。

如果是全内存数据库，或者索引可以长期驻留在内存中，那么也可以考虑其他更高效的结构，比如 Hash 索引、Trie 类索引（例如 DuckDB 中的 ART）。

关于 B-Tree 的现代改进，可以参考 SIGMOD 2025 的论文《B-Trees Are Back》及其参考文献，以及这篇论文解读。

Questions:

PostgreSQL 中的 CREATE INDEX CONCURRENTLY（CIC）并不阻塞读写操作，那么它是如何实现的？

提示：实际上存在短暂阻塞操作