一直只知道数据库索引可以提高查询效率，但数据库索引具体的实现一直不太清楚，看了一些文章，这里进行一个总结。

本文的目的是对数据库索引的基本概念进行介绍，不进行深入的探讨。

一、索引的概念

索引是定义在存储表基础之上，有助于无需检查所有记录而快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的**索引项(index entries)**组成。索引项由两部分组成：

• 索引字段：table中的某些列，如id等；类似于词典中的词条
• 索引指针：指向table中包含索引字段值的记录在磁盘上的存储位置。类似于词典中词条对应的页码

二、索引的分类

按不同分类方法， 索引可以分为：稠密索引与稀疏索引（数据与索引的对应关系）、主索引与辅助索引、聚簇索引与非聚簇索引（数据与索引的存储顺序）、倒排索引、多级索引、散列索引等等。

表：几种索引类型表``

索引类型	概念	特点
稠密索引	对于主文件中每一个记录（形成的每一个索引字段值），都有一个索引项和他对应，指明该记录的位置	查询效率高，但占用空间大，维护任务大
稀疏索引	对于主文件中部分记录（形成的索引字段值），有索引项和他对应	空间占用少，维护任务更轻，但速度更慢
主索引	对每一个存储块有一个索引项，索引项的总数和存储表所占的存储块数目相同。	- 属于稀疏索引；
辅助索引	**是定义在主文件的任一或多个非排序字段上的辅助存储结构。**辅助索引通常是对某一非排序字段上的每一个不同值有一个索引项：索引字段即是该字段的不同值；	属于稠密索引
聚簇索引	在索引中邻近的记录在主文件中也是邻近存储的；	通常是主索引
非聚簇索引	在索引中邻近的记录在主文件中不一定是邻近存储的；	通常是非聚簇索引
.....

B+树索引

B+树索引，是一种多级索引，当索引项比较多时候，可以对索引在建立索引，依次类推，形成多级索引。

注：非叶节点指针指向索引块，叶结点指针指向主文件的数据块或数据记录

特点：

• 能够自动保持与主文件大小相适应的树的层次
• 每个索引块的指针利用率都在50%-100%之间

三、sqlserver中的索引

1、数据表基本结构

Sqlserver借鉴了操作系统的虚拟内存的概念，人为的将文件划分N个8KB的存储空间，SQL Server用8KB的页来存储数据。（页是sqlserver最小存储单元）

页有不同的类型，包括数据页、索引页、GAM等等（满足不同类型数据存储的需要）。

以下是sqlserver中的页类型：（关于不同页的具体内容，不是本篇文章的重点，这里不做介绍，~其实是因为自己不会）

• 1 Data page，数据页 堆表和聚集索引的叶子节点数据
• 2 **Index page，索引页 ** 聚集索引的非叶子节点和非聚集索引的所有索引记录
• 3 Text mixed page A text page that holds small chunks of LOB values plus internal parts of text tree. These can be shared between LOB values in the same partition of an index or heap.
• 4 Text tree page A text page that holds large chunks of LOB values from a single column value.
• 7 Sort page 排序时所用到的临时页，排序中间操作存储数据用的。
• 8 GAM page全局分配映射（Global Allocation Map，GAM）页面 这些页面记录了哪些区已经被分配并用作何种用途。
• 9 SGAM page共享全局分配映射（Shared Global Allocation Map，GAM）页面 这些页面记录了哪些区当前被用作混合类型的区，并且这些区需含有至少一个未使用的页面。
• 10 IAM page 有关每个分配单元中表或索引所使用的区的信息
• 11 PFS page有关页分配和页的可用空间的信息
• 13 boot page 记录了关于数据库的信息，仅存于每个数据库的第9页
• 15 file header page 记录了关于数据库文件的信息，存于每个数据库文件的第0页
• 16 DCM page 记录自从上次全备以来的数据改变的页面，以备差异备份
• 17 BCM page 有关每个分配单元中自最后一条 BACKUP LOG 语句之后的大容量操作所修改的区的信息

数据页

数据页由3个部分组成。页头（标头），数据区（数据行和可用空间，实际数据存储位置）及行偏移数组。

2、聚集索引

在SQL Server数据库中，索引的存储是以B+树结构来存储的。

聚集索引是一种对磁盘上实际数据重新组织以按指定的一列或多列值排序。由于在聚集索引下，数据在物理上是按序排列在数据页上的，重复值也排在一起，因而包含范围检查（bentween,<,><=,>=）或使用group by 或order by的查询时，一旦找到第一个键值的行，后面都将是连在一起，不必在进一步的搜索，避免大范围的扫描，可以大大提高查询速度。

聚集索引存储结构：

• 聚集索引的根节点和中间节点是索引页，都只包含下一层的入口指针和入口值（位于存储位置的第一个主键值）；
• 聚集索引的叶节点就是数据页。存放了表里所有字段的数据

3、非聚集索引

非聚集索引不重新组织表中的数据，而是对每一行存储索引列值并用一个指针指向数据所在的页面。

非聚集索引存储结构：

• 非聚集索引的根节点和中间节点是索引页，都只含下一层级的入口指针和入口值（位于存储位置的第一个键值）；
• 非聚集索引的叶节点也是索引页*，也存储有聚集索引和非聚集索引的键值；
• 非聚集索引中的每个索引行（不论是根节点、中间节点还是叶节点）都包含非聚集键值和行定位符，此定位符指向聚集索引或堆（没有聚集索引的表）中包含该键值的数据行。

四、什么时候建立索引

索引技术应用可以使得检索效率大大提高，但同时其增加了存储空间，使维护负担加重（不仅要维护主文件，而且要维护索引文件），而且聚集索引每张表只能有一个，因此在什么字段上建立索引和建立什么样的索引尤为重要。

一般建立索引的原则包括以下内容：

• 大的原则:经常出现在检索条件，连接条件，分组计算条件中的属性应该建立聚集索引；
• 在一个经常做插入操作的表中建立索引，应使用fillfactor(填充因子)来减少页分裂，同时提高并发度降低死锁的发生。如果在表为只读表，填充因子可设为100；
• 在选择索引键时，尽可能采用小数据类型的列作为键以使每个索引页能容纳尽可能多的索引键和指针，通过这种方式，可使一个查询必需遍历的索引页面降低到最小，此外，尽可能的使用整数做为键值，因为整数的访问速度最快；
• 如果大多数处理都只涉及某个大表的某些列，可以考虑为这些列建立覆盖索引；

一些误区：

• 自增类型的主键id作为聚集索引

通常情况下，我们会在每张表中建立一个id作为主键，但检索的时候如果不用id号来进行查询的话，就失去了作为聚集索引的意义，浪费了聚集索引这一宝贵的资源

强烈建议哈工大的《数据库系统》课程，中国大学MOC和B站上都有课程视频

参考： 聚集索引与非聚集索引的总结 https://www.cnblogs.com/s-b-b/p/8334593.html

数据库索引 https://www.cnblogs.com/amou/p/9523166.html#autoid-0-0-0

SqlServer索引的原理与应用  https://www.cnblogs.com/knowledgesea/p/3672099.html

SQL Server 存储(1/8)：理解数据页结构   https://blog.csdn.net/yangmeng518889/article/details/53911006