PostgreSQL 技术内幕：索引扫描

索引概述
数据库索引是一种数据库对象，用于重新组织表中特定字段中的数据。通过使用索引，数据库中的一些操作可以大大加速。其背后的想法也很简单：空间换时间。

数据库中的索引可以与书籍的目录进行比较。当我们查询书中的某些信息时，我们可以利用目录快速找到相应的章节，从而避免了翻阅整本书的需要。加快搜索过程。

索引分类
Postgres中常见的索引一般包括以下类型。其中BTree索引应用最广泛，也是创建索引时的默认选项。

索引扫描示例
我们通过一个例子来了解一下索引对表扫描性能的影响。我们首先创建一个测试表，例如称为articles，并向其中插入一些测试数据。

CREATE TABLE articles (  id SERIAL8 NOT NULL PRIMARY KEY,  a text,  b text,  c text);INSERT INTO articles(a, b, c)SELECTmd5(random()::text),md5(random()::text),md5(random()::text)from (  SELECT * FROM generate_series(1,1000000) AS id) AS x;

我们从这个表中查询一条数据，例如查找数据a = '65c966eb2be73daf418c126df8dc33b5'。查询计划如下：

可以看到这里使用的是顺序扫描（Seq Scan），成本（Cost）为22450。如果我们给a字段添加索引（默认是BTree），创建对文章(a)建立索引，然后运行这条sql语句，查询计划如下：

可以看到这里使用了索引扫描（ Index Scan ），成本为8。顺序扫描22450个查询成本显着降低，查询性能显着提升。

扫描方法
顺序扫描
对于未索引字段的查询，或者当估计查询将返回最多数据时，查询优化器将使用顺序扫描方法。仍然以上一篇文章的表为例，这里我们查询的是id>100的数据，该数据包含了表中最多的数据，所以即使id列上有索引，仍然会采用顺序扫描。

索引扫描
如果预计查询会命中极少量的数据，查询优化器会选择索引扫描方法。上面的例子有相应的显示。下面是扫描索引范围的示例。可以看到命中数据占表数据的比例很小。选择索引扫描是最有效的。？较小。因此，当命中中等数据（在少量和多数之间）时，顺序扫描和索引扫描各有其缺点。对于这种情况，一般可以采用位图索引扫描。原理是对要访问的页面进行排序，将随机IO转换为顺序IO。

一般操作步骤如下：

• 使用索引扫描所有符合条件的TID
• 使用TID列表根据页面访问顺序构建位图。读取数据记录时，同一页只需
• 读取一次Tag即可。下图描述了Postgres中的几种表数据扫描方法。查询优化器根据计算成本选择最佳扫描方法。
  
  索引物理存储 postgres中的索引是二级索引，即在物理存储上索引数据和对应的表数据是分开的。每个具体的索引对象都存储为一个独立的关系表，可以在pg_class系统表中查询。
  
  以BTree为例，其大体结构如下：

  B+树一般特点：

• 树的层级较少：每个内部数据节点不再存储。可存储的值会更多，导致树的层数更少，数据查询更快（随机IO更少）。
• 查询速度更稳定：由于所有数据驻留在叶子节点上，因此每次搜索次数（树的高度的随机IO操作）相同，查询速度也更稳定。
• 遍历查询更方便：B+Tree的叶子节点数据形成有序链表。遍历查询时，首先找到第一个键值的位置，然后沿着链表访问所有数据。 BTree 中的每个节点在物理结构中都存储为页。页的结构与堆表类似如下：
  
  以 BTree 为例，索引的内容可以理解为元组 TID 的数据 Map 的键值，其中 TID 为块号和偏移量。 ？表中的数据构建了完整的B-Tree索引。
  main函数的调用路径如下：

ProcessUtility() Utility语句的处理入口DefineIndex() 定义一个索引（异常判断，准备index_create()的输入参数）index_create() 创建一个索引（建立关系文件并更新系统表数据）index_build() 构建索引的外层接口bt_build() B-Tree的索引构建逻辑

以BTree为例，利用表中的数据构建B-Tree索引一般分为两步。一种是对表中的数据进行排序，另一种是按照顺序对数据进行排序。从下到上遍历数据元组构建整个BTree。这里的主要目的是针对不同的索引类型调用不同的 ambuild 方法。 BTree 的等效方法是 btbuild。下图展示了索引相关接口的访问比例。通过IndexAM抽象出各种索引访问方法，可以由上层的执行来调用。 ？ ExecInitIndexScan
主要负责索引扫描初始化 状态结构IndexScanState的核心任务是将索引扫描的过滤条件转换为不同类型的扫描键ScanKey。

• ScanKey主要存储索引列信息、操作函数和待比较函数。 ScanKey描述了一个完整的过滤条件，用于索引扫描
• 但如果过滤条件是复杂的表达式，则需要引入iss_RuntimeKeys。处理
  IndexScanState 中的关键字段：

Init 阶段的主要重点是 ExecIndexBuildScanKeys 方法。该方法的作用是将扫描过滤条件转换为不同类型的扫描键ScanKeys。

索引的过滤条件分为以下五种情况：

• 常量或常用操作，直接存储在ScanKey中
• 非常值表达式操作，此时执行节点无法检索到其中的表达式初始阶段因此需要临时存储iss_RuntimeKeys
• RowCompareExpr。例如，过滤条件为“(indexkey1,indexkey2) > (1, 2)”，表示多个过滤条件的组合。它会遍历所有子过滤条件并将其存储在 iss_ScanKeys 或 iss_RuntimeKeys
• ScalarArrayOpExpr 中，例如过滤条件为“indexkey1 = ANY (1,10,20)”，如果索引支持基于矩阵的搜索处理，则存储常量分别在 ScanKey 或 RuntimeKey 中，如果不支持数组搜索，如 Hash、GIN、Gist 索引，那么将过滤条件存储在 arrayKeys
• NullTest 中，无论索引 key 是否为 NULL，例如_"indexkey IS NULL/ IS NOT NULL”，只需设置 ScanKey_

ExecIndexScan
对应的值即可。 负责根据索引读取元组并返回到执行器的顶层节点。 IndexNext函数不断进行索引扫描，读取元组，并将元组封装在TupleTableSlot中并发送给上层节点。 ？在pg_am表中找到amgettuple对应的内部接口函数
。调用该函数（如BTree中的btgettuple），根据具体索引实现返回一个TIME。

ExecEndIndexScan
主要负责清理工作，释放内存上下文用于计算RuntimeKey并关闭相关索引表和数据表。