什么是索引？索引的目的及优缺点？PostgreSQL中的索引及分类索引是指按表中某些关键属性或表达式建立元组的逻辑顺序，它是由一系列表元组的标识号组成的一个列表。

在关系数据库中，索引是一种与表有关的数据库结构，它可以使对应于表的SQL语句执行得更快。

索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

索引的分类按存储结构区分：“聚集索引（又称聚类索引，簇集索引）”，“分聚集索引（非聚类索引，非簇集索引）”按数据唯一性区分：“唯一索引”，“非唯一索引”按键列个数区分：“单列索引”，“多列索引”。

为什么要创建索引呢？这是因为，创建索引可以大大提高系统的性能。

第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

第二，可以大大加快数据的检索速度，这也是创建索引的最主要的原因。

第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

第四，在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

也许会有人要问：增加索引有如此多的优点，为什么不对表中的每一个列创建一个索引呢？这种想法固然有其合理性，然而也有其片面性。

虽然，索引有许多优点，但是，为表中的每一个列都增加索引，是非常不明智的。

这是因为，增加索引也有许多不利的一个方面。

第一，创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。

第二，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引是建立在数据库表中的某些列的上面。

因此，在创建索引的时候，应该仔细考虑在哪些列上可以创建索引，在哪些列上不能创建索引。

一般来说，应该在这些列上创建索引，例如：在经常需要搜索的列上，可以加快搜索的速度；在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

PostgreSQL中五种索引方式：唯一，主键，多属性，部分，表达式四种索引类型：B-Tree，Hash，Gist，GINCREATE INDEX用于创建索引，默认创建一个B-Tree索引相关系统表：每种索引类型在系统表pg_am中用一个元组记录，共4个元组对应类型，其中记录了可被调用的接口函数和相关属性，共有13种函数类型。

每一个创建的索引，会在pg_class系统表中添加一个元组，同时在pg_index中添加一个元组。

Pg_index用于记录与索引有关的信息。

每一种索引类型并不直接设定其所操作的数据类型，而是由操作符系统表pg_opclass 管理，而每一个操作符类引用了pg_opfamily一个元组Pg_amop中存每个索引操作符集合(pg_opfamily)与具体操作符（pg_operator）关联信息Pg_amproc则存储集合与其相关联的支持过程或函数（pg_proc）关联信息例：Pg_proc中一个函数属于pg_opfamily一个集合，则pg_amproc中就有一个元组记录这个对应关系。

B-TreeM为树的阶数，B-树或为空树，否则满足下列条件：1.定义任意非叶子结点最多只有M个儿子；且M>2；2.根结点的儿子数为[2, M]；3.除根结点以外的非叶子结点的儿子数为[M/2, M]；4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字,根节点至少一个关键字）；5.非叶子结点的关键字个数=指向儿子的指针个数-1；6.非叶子结点的关键字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1] ；7.非叶子结点的指针：P[1], P[2], …, P[m]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；8.所有叶子结点位于同一层；如：（M=3）M=3的B-树B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

特性1.关键字集合分布在整颗树中；2.任何一个关键字出现且只出现在一个结点中；3.搜索有可能在非叶子结点结束；4.其搜索性能等价于在关键字全集内做一次二分查找；大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树B+树的定义B+树是应文件系统所需而出的一种B-树的变型树。

一棵m阶的B+树和m阶的B-树的差异在于：1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

a) 为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？1) B+-tree的磁盘读写代价更低B+-tree的内部结点并没有指向关键字具体信息的指针。

因此其内部结点相对B 树更小。

如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。

一次性读入内存中的需要查找的关键字也就越多。

相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。

一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。

而B+ 树内部结点只需要1个盘快。

当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2) B+-tree的查询效率更加稳定由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。

所以任何关键字的查找必须走一条从根结点到叶子结点的路。

所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

读者点评数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。

正是为了解决这个问题，B+树应运而生。

B+树只要遍历叶子节点就可以实现整棵树的遍历。

而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

看完索引的整体逻辑过程（创建，插入，扫描，删除）感觉整体性很强，都是有一个总流程，之后函数+数据结构实现相关模块，逻辑性较强，涉及函数较多。

创建索引：将待索引的表元组封装为索引元组，并进行排序，之后填充入叶子节点，填充满则申请新的叶子节点，并在父节点中添加指针，重复该过程。

插入过程中，主要涉及查找及可能进行的叶子节点分裂。

其中，为了减少分裂操作，设置一个百分比填充因子（留下冗余量），虽然带来一定空间浪费，但可以避免过于频繁的分裂。

Hash索引：Hash相对比较熟悉。

在hash表中，有一个函数以查找键为参数，计算出0~b-1（b 是桶的数目）B的数目是否变化，分为静态与动态。

PostgreSQL使用动态hash（可扩展/线性）实现中包含两种类型hash，一个是用作索引的外存，另一种用于内存查找元页记录相关信息，每次对索引读写操作都要将元页读入内存Hash表多个桶组成，每个桶含一或多个页，每个桶第一页称为桶页，其他页称为溢出页。

桶页成组分配，每次分配2的幂次。

0，1号初始化分配。

每次分配的桶页磁盘上连续存储。

溢出页分配在每次分配整体后。

（例：4~7桶中，4满了，溢出页加在7后）溢出页和桶页之间双向链表，溢出页一旦分配，一直存在，不会释放物理空间（为了快速计算桶标号）位图用于标记每个溢出页是否可用下面举例说明hash表不断插入时各种页面分配情况：①初始化。

0号块元页，1,2号块分配给0,1号桶，并在桶后分配位图页（3号块）②增加两个溢出页。

磁盘号为45.③增加一个桶。

增加2号桶需要分裂，其实增加了2,3号桶，但3号先不投入使用。

④为2号桶增加溢出页Hash的实现：构建，元组插入，溢出页管理，hash表扩展构建：初始化，之后扫描要索引的表，生成索引元组，最后插入到hash溢出页的分配回收需要考虑共享问题，设置排他锁Hash表扩展，每次插入，计算当前记录r/桶数n，比例太大就要进行扩展和压缩。

GiST通用搜索树，是一种平衡的树状结构访问方法，相当于一个基础模板，可以用它实现任意索引模式。

它可以建立一种可扩展的索引结构，包括数据类型和查询谓词扩展。

Gist接口提供了高层抽象，只要求实现基本语义，而不用理解数据库内部工作机制。

可以根据相关领域设定数据或谓词，多用于图像处理GIN通用倒排索引，是一个存储（key，posting list）集合的索引结构，key是键值，posting list 是出现过key的位置，位置由“元组ID：位置”表示如（”hello”,”14:17,…”）表示hello关键字在14号元组被索引属性第17个位置出现。

通过这种结构可快速查找包含关键字的元组，特别适合支持全文搜索。

GIN包含四部分：Entry：一个词位/键值Entry tree：在entry上构建的b树Posting tree：在一个entry出现的物理位置上构建的b树Postling list：entry物理位置列表GIN索引适合静态的数据因为查找是迅速的. 对于动态数据, GiST 可以更快的更新. 具体来说, GiST索引在动态数据上是好用的并且如果单独的字（词位）在100,000以下也是快速的,然而GIN 索引在处理100,000词位以上时是更好的但是更新就要慢点了.TSearch2 全文搜索全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。