《PostgreSQL数据库内核分析》之索引（四）
【摘要】 PostgreSQL支持的索引有：B-Tree、Hash、GiST（搜索树）、GIN（倒排）索引索引的5种方式：唯一索引、主键索引、多属性索引、部分索引和表达式索引4.1概述pg所有索引都是“从属索引”，索引在物理上与它描述的表文件分离。每个索引都在pg_class表里面有记录，一个索引的内部结构与该索引的访问方法（索引类型）相关。pg中所有索引访问方法通过页面来组织索引的内部结构，这样可以...
PostgreSQL支持的索引有：B-Tree、Hash、GiST（搜索树）、GIN（倒排）索引
索引的5种方式：唯一索引、主键索引、多属性索引、部分索引和表达式索引
4.1概述
pg所有索引都是“从属索引”，索引在物理上与它描述的表文件分离。
每个索引都在pg_class表里面有记录，一个索引的内部结构与该索引的访问方法（索引类型）相关。pg中所有索引访问方法通过页面来组织索引的内部结构，这样可以使用存储管理器提供的接口来访问索引。
索引从本质上来说就是一些数据的键值与元组标识符（TID）之间的映射，这些标识符确定了该索引键值在表中对应的元组。
4.1.1索引方式
1.唯一索引：B-Tree可创建唯一索引
2.主键索引：主键索引是唯一索引的特殊类型
3.多属性索引：一个索引被定义在多于一个的属性上，就称其为多属性索引 多用于组合查询 多属性索引不仅可以使用表中的属性，也可以使用函数或表达式计算得到的值
4.部分索引：建立在一个表的子集上的索引 通过表达式来限制被索引的元组的数量
5.表达式索引：并非建立在一个表的属性上，还可以建立在一个函数或从表中一个或多个属性计算出来的标量表达式上 用表达式来计算被索引元组的键值
4.1.2索引类型
1.B-Tree：适合支持比较查询级范围查询。 pg的优化器会考虑使用B-Tree索引进行查找。
2.Hash: 使用Hash函数对索引的关键字进行散列。Hash索引只能处理简单的等于比较。
3.GiST: 搜索树。是一种架构或索引模板。可在这种架构（模板）上实现不同的索引策略。可使用GiST索引的操作符类型高度依赖于索引策略（操作符类）
4.GIN: 倒排索引。可处理包含多个键的值（比如数组）。支持用户定义的索引策略，对于不同的索引策略，可使用的操作符也是不同的。
4.1.3索引相关系统表
pg_am
pg_index 记录与索引有关的信息
pg_opclass 操作符类系统表
pg_opfamily pg_class中，每一个操作符类都引用了系统表pg_opfamily的一个元组，表明该操作符类的操作符集合。
pg_amop：存储每个索引操作符集合（pg_opfamily）与具体的操作符（pg_operator）的关联关系
pg_amproc: 存储每个索引操作符集合（pg_family表）与其他关联的支持过程或函数（pg_proc）的关联信息
4.1.4索引的操作函数
每一种索引类型可以实现ambuild、aminsert、ambulkdelete、amvacuumcleanup、amcostestimate、amoptions、ambeginscan、amgettuple、amgetbitmap、amrescan、amendscan、ammarkpos和amrestrpos共13个函数，会有相应的13个函数来实现这些接口。注意，这13个接口并不要求每一种索引类型全部实现，每一种索引类型可以有选择地实现其中的某些接口。当其他模块需要使用索引时，将会根据索引的类型找到pg_am中对应的元组，然后再该元组中找到适当的操作函数来完成所需的操作。
4.2B-Tree索引
4.2.1B+树
1.特点
1）关键字均在叶子节点，按关键字排序以顺序链的方式链接，同时，叶子节点还保存了指向相应记录的指针
2）所有非叶子节点可看作索引部分，并不指向实际的存储位置；非叶子节点中仅仅包含其子树节点中最小的关键字
B+树查找，无论查找成功与否，每次查找都是经过一条从根到叶子节点的路径
不管是内部节点还是叶子节点，都有一个指针指向兄弟节点
4.2.2B-Tree索引的组织结构
PostgreSQL中，索引按照下图中的页面结构进行存储
B-Tree索引的组织结构
4.2.3B-Tree索引的操作
1.索引的创建
对每一个需要索引表的元组生成对应的索引元组，然后调用tuplesort函数对所有的索引元组进行排序，最后创建索引。
索引元组由IndexTupleData进行存储，该结构包括了一些该索引元组所指向的表元组以及一些索引元组的信息
BTWriteState结构：记录整个索引创建过程中的信息
对于树结构中的每一层都会生成一个结构BTPageState，使用btps_next指针来指向父节点的目的是：当该节点中关键字变化导致需要调整父节点中的关键字时，可通过该指针快速定位到父节点
2.插入索引元组
新插入的元组封装成索引元组并插入到索引中，这个过程由btinsert函数完成
btinsert会将表元组封装为索引元组，然后沿着B-Tree往下找到合适的插入点，找到正确节点后，若该索引关系是唯一索引，则会在节点中验证待插入的元组是否已存在。若存在则报错结束，若索引不是唯一索引或没有重复元组，则将索引元组插入索引中。
3.扫描索引
B-Tree进行范围查询时，首先要对索引进行扫描，在PostgreSQL中，与扫描相关的函数主要有：
btgettuple函数：
btbeginscan：
btrescan：
btendscan：
btmarkpos：
btrestrpos：
4.删除索引元组
btvacuumcleanup：寻找可以删除的页面
btbulkdelete：批量删除指向一个表元组集合所对应的所有索引元组
在B-Tree索引中，由函数btbulkdelete通过扫描索引确定基本表中哪些元组被删除，而后逻辑上删除（标记删除）那些元组对应的索引元组，最后由VACUUM在物理上删除。
4.3Hash索引
Hash表可以把键值分配到各个桶中
Hash表有静态（桶数目不变）和动态（允许桶数目改变）区分，PostgreSQL中使用的是动态的Hash表，桶的个数随着分裂次数的增加而增加。
4.3.1Hash索引的组织结构
PostgreSQL 8.4.1的实现中包含两种类型的Hash表，一个是用做索引的外存Hash表，另一个是用于内部数据查找的内存Hash表
1.元页
每个Hash所有都有一个元页，元页中记录了Hash的版本号、Hash索引记录的索引元组数目、桶的信息、位图等相关信息。通过元页可了解该Hash索引在总体上的分配和使用情况，在索引元组中插入、溢出页的分配回收以及Hash表的扩展等过程中，都需要使用元页
Hash索引初始化时会将已知的关于即将建立的索引信息都写到元页中去。
2.桶页
Hash表由多个桶组成，每个桶由一个或多个页组成，每个桶的第一页称为桶页，其他页称为溢出页，桶页随着桶的建立而建立。桶页结构中的HashPageOpaqueData.hasho_bucket为该桶的标识，若该桶有溢出页，字段hasho_nextblkno指向溢出页，用于构建桶页的链结构，实现快速查找。
桶页是成组分配，每次分配的数目都是2的幂次。
3.溢出页
若某个元组的在它所属的桶中放不下时，需要给该桶增加一个溢出页。溢出页和桶页之间是通过双向链链接起来的，即每一页都记录了前一页的块号（prevblkno）和后一页的块号（next-blkno），这个双向链保存在HashPageOpaqueData结构中。当溢出分配给某个桶页使用时，溢出页的HashPageOpaqueData.hasho_bucket将设置为桶页的块号。
当该桶存放的记录已达到饱和时，以后插入到该桶中的记录会添加到该桶的溢出页中，而溢出页通过双向指针与桶页链接，可灵活实现查找、删除等操作。
4.位图
管理Hash索引的溢出页和位图页本身的使用情况。若某个溢出页上的元组都被移除或删除，就要将此溢出页回收，但并不把它还给操作系统，而继续由PostgreSQL管理，以便下次需要溢出页时使用。因此，需要一种机制来记录每一个溢出页是否可用，用到位图。
4.3.3Hash索引的实现
1.Hash表的创建
初始化索引的元页、桶及位图页。调用扫描函数对待索引的表进行扫描，生成对应的索引元组，最后将这些索引元组插入Hash表中。
2.索引元组的插入
完成元页初始化，根据查找键生成索引元组后，可调用函数将该索引元组插入到Hash表中
因为插入操作并不会改变桶中已存在的元组的位置，所以插入操作可以和扫描操作并发进行。
3.溢出页的分配与回收
在索引元组的插入过程中，若待插入的桶中没有空间，就需要创建一个溢出页，并把它连接到该桶上，然后将索引元组插入到分配的溢出页中。当对Hash表进行扩展之后，原来存放溢出页中的索引元组可能就会移动到新增加的桶中，这时就需要对溢出页进行回收。
4.4GiST索引
GiST(Gereralized Search Tree,通用搜索树)是一种平衡的、树状结构的访问方法。在系统中相当于一个基础的模板，几乎可以使用它实现任意索引模式。可建立一种可扩展的索引结构，包括树类型和查询谓词的扩展。
GiST允许用户（并非数据库专家）开发自己的数据类型，并通过相应的访问方法来在该数据类型上使用GiST索引。
4.5GIN索引
GIN(Generalized Inverted Index，通用倒排索引)是一个存储对（key，posting list）集合的索引结构，其中“key”是一个键值，“posting list”是一组出现过“key”的位置
4.6TSearch2全文索引
全文搜索一般有三个步骤：
1）对文档（文本）进行预处理，得到处理后的结果，创建索引
2）解析查询条件，使用索引进行查询
3）得到查询结果，对结果进行处理后返回
PostgreSQL提供了一个树类型tsvector用于存储预处理后的文档，还提供了一个数据类型tsquery用于查询（还为这两种类型提供了匹配操作符@@）以及查询结果的处理。
小结
索引是提高数据库性能的常用方法，可令数据库服务器以更快的速度查找和检索特定的行。不过索引也增加了数据库系统的负荷，因此应该恰当地使用它们。索引的优劣不仅仅与索引的查询效率有关，同时与索引创建速度、更新速度，索引大小等因素有关。以上分析的几种索引使用环境不同，相同环境下使用的优劣也各不相同。于是，为了方便用户对特殊数据类型数据的查询，PostgreSQL中提供了索引模板可方便用户对索引的拓展及支持自定义数据类型上的索引创建与查询。
通过使用索引，能快速查找数据库中的数据。但在添加索引的同时，会增加数据库系统的负荷；在增删改数据时，维护索引的一致性也需要一定的时间和空间。由于索引给查找数据带来巨大的性能提升，因此也得到了广泛的应用。在实际的使用中，应该合理权衡适应索引带来的利弊，恰当地使用索引。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）