在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。
索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。
当表中有大量记录时，若要对表进行查询，第一种搜索信息方式是全表搜索，是将所有记录一一取出，和查询条件进行一一对比，然后返回满足条件的记录，这样做会消耗大量数据库系统时间，并造成大量磁盘I/O操作；第二种就是在表中建立索引，然后在索引中找到符合查询条件的索引值，最后通过保存在索引中的ROWID（相当于页码）快速找到表中对应的记录。
1、定义概念
索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。索引是针对表而建立的，它是由数据页面以外的索引页面组成的，每个索引页面中的行都会含有逻辑指针，以便加速检索物理数据。
在数据库关系图中，可以在选定表的“索引/键”属性页中创建、编辑或删除每个索引类型。当保存索引所附加到的表，或保存该表所在的关系图时，索引将保存在数据库中。
2、作用
在数据库系统中建立索引主要有以下作用：
（1）快速取数据；
（2）保证数据记录的唯一性；
（3）实现表与表之间的参照完整性；
（4）在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。
3、优缺点
优点
1.大大加快数据的检索速度;
2.创建唯一性索引，保证数据库表中每一行数据的唯一性;
3.加速表和表之间的连接;
4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。
缺点
1.索引需要占物理空间。
2.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。
4、索引类型
根据数据库的功能，可以在数据库设计器中创建四种索引：单列索引、唯一索引、主键索引和聚集索引。
普通索引
最基本的索引类型，没有唯一性之类的限制。普通索引可以通过以下几种方式创建：
创建索引，例如CREATE INDEX <索引的名字> ON tablename (列的列表)；
CREATE INDEX index_name ON table_name (column_name)
修改表，例如ALTER TABLE tablename ADD INDEX [索引的名字] (列的列表)；?
创建表的时候指定索引，例如CREATE TABLE tablename ( [...], INDEX [索引的名字] (列的列表) )；
唯一索引
唯一索引是不允许其中任何两行具有相同索引值的索引。
当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如，如果在 employee 表中职员的姓 (lname) 上创建了唯一索引，则任何两个员工都不能同姓。
对某个列建立UNIQUE索引后，插入新记录时，数据库管理系统会自动检查新纪录在该列上是否取了重复值，在CREATE TABLE 命令中的UNIQUE约束将隐式创建UNIQUE索引。
创建唯一索引的几种方式：
创建索引，例如CREATE UNIQUE INDEX <索引的名字> ON tablename (列的列表)；
修改表，例如ALTER TABLE tablename ADD UNIQUE [索引的名字] (列的列表); ；
创建表的时候指定索引，例如CREATE TABLE tablename ( [...], UNIQUE [索引的名字] (列的列表) )；
主键索引
简称为主索引，数据库表中一列或列组合（字段）的值唯一标识表中的每一行。该列称为表的主键。
在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。
提示尽管唯一索引有助于定位信息，但为获得最佳性能结果，建议改用主键索引。
候选索引
与主键索引一样要求字段值的唯一性，并决定了处理记录的顺序。在数据库和自由表中，可以为每个表建立多个候选索引。
例如下面这张表的候选键
聚集索引
也称为聚簇索引，在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引， 即如果存在聚集索引，就不能再指定CLUSTERED 关键字。
索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。聚集索引更适用于对很少对基表进行增删改操作的情况。
如果在表中创建了主键约束，SQL Server将自动为其产生唯一性约束。在创建主键约束时，指定了CLUSTERED关键字或干脆没有制定该关键字，SQL Sever将会自动为表生成唯一聚集索引。
?特点
- 每张表只能建一个聚集索引，日志型存储引擎 tukodb 除外；
- innodb 中，聚集索引就是表，表就是聚集索引；
- myisam 没有聚集索引的概念。
聚集索引的优先选择列
- 含有大量非重复值的列
- 使用 between，》或《返回一个范围值的列
- 被连续（顺序）访问的列
- 返回大量结果集的查询
- 经常被 join 的列
不建议的聚集索引列
- 修改频繁的列
- 唯一值很小的列
- 新增内容太过离散随机的列
非聚集索引
也叫非簇索引，在非聚集索引中，数据库表中记录的物理顺序与索引顺序可以不相同。一个表中只能有一个聚集索引，但表中的每一列都可以有自己的非聚集索引。如果在表中创建了主键约束，SQL Server将自动为其产生唯一性约束。在创建主键约束时，如果制定CLUSTERED关键字，则将为表产生唯一聚集索引。
Mysql中的聚集索引和非聚集索引
MySQL的Innodb存储引擎的索引分为聚集索引和非聚集索引两大类，理解聚集索引和非聚集索引可通过对比汉语字典的索引。汉语字典提供了两类检索汉字的方式，第一类是拼音检索（前提是知道该汉字读音），比如拼音为cheng的汉字排在拼音chang的汉字后面，根据拼音找到对应汉字的页码（因为按拼音排序，二分查找很快就能定位），这就是我们通常所说的字典序；第二类是部首笔画检索，根据笔画找到对应汉字，查到汉字对应的页码。拼音检索就是聚集索引，因为存储的记录（数据库中是行数据、字典中是汉字的详情记录）是按照该索引排序的；笔画索引，虽然笔画相同的字在笔画索引中相邻，但是实际存储页码却不相邻，这是非聚集索引。
5、操纵索引
维护和使用
DBMS自动完成维护和自动选择是否使用索引以及使用哪些索引。
创建索引
SQL3没有提供建立索引的方法。但是，从事DBMS开发、销售的公司都提供他们具有这种功能的SQL工具。因为这些工具不是标准化的，它们相互不同。SQL语言使用CREATE INDEX 语句建立索引，其一般格式是：
CREATE [UNIQUE] [CLUSTERED| NONCLUSTERED] INDEX <索引名>
ON <表名>(<列名>[ASC|DESC] [, <列名>[ASC|DESC]...])
说明：与表一样，索引也需要有唯一的名字，且基于一个表来建立，可以根据表中的一列或者多列，当列的顺序都是升序默认可不必标出，当属性列有按照降序排列的，所有属性的升序降序都不要标明。
UNIQUE——建立唯一索引。
CLUSTERED——建立聚集索引。
NONCLUSTERED——建立非聚集索引。
ASC——索引升序排序。
DESC——索引降序排序。
修改索引
对于已经建立的索引，如果需要对其重新命名，可以使用ALTER INDEX 语句。其一般格式为
ALTER INDEX <旧引索名字> RENAME TO<新引索名>
删除索引
当某个时期基本表中数据更新频繁或者某个索引不再需要时，需要删除部分索引。SQL语言使用DROP INDEX 语句删除索引，其一般格式是：
DROP INDEX<索引名>
删除索引时，DBMS不仅在物理删除相关的索引数据，也会从数据字典删除有关该索引的描述。
6、注意事项
并非所有的数据库都以相同的方式使用索引。作为通用规则，只有当经常查询索引列中的数据时，才需要在表上创建索引。索引占用磁盘空间，并且降低添加、删除和更新行的速度。如果应用程序非常频繁地更新数据或磁盘空间有限，则可能需要限制索引的数量。在表较大时再建立索引，表中的数据越多，索引的优越性越明显。
可以基于数据库表中的单列或多列创建索引。多列索引使您可以区分其中一列可能有相同值的行。
如果经常同时搜索两列或多列或按两列或多列排序时，索引也很有帮助。例如，如果经常在同一查询中为姓和名两列设置判据，那么在这两列上创建多列索引将很有意义。
确定索引的有效性：
检查查询的 WHERE 和 JOIN 子句。在任一子句中包括的每一列都是索引可以选择的对象。
对新索引进行试验以检查它对运行查询性能的影响。
考虑已在表上创建的索引数量。最好避免在单个表上有很多索引。
检查已在表上创建的索引的定义。最好避免包含共享列的重叠索引。
检查某列中唯一数据值的数量，并将该数量与表中的行数进行比较。比较的结果就是该列的可选择性，这有助于确定该列是否适合建立索引，如果适合，确定索引的类型。
7、B+TREE
B+树的特点：
- 中间元素不存数据，只是当索引用，所有数据都保存在叶子结点中。
- 所有的中间节点在子节点中要么是最大的元素要么是最小的元素 。
- 叶子结点包含所有的数据，和指向这些元素的指针，而且叶子结点的元素形成了自小向大这样子的链表。
如下这个图就很好的说明了B+的特点
看图其实可以看到一个节点可以存放多个数据，查找一个节点的时候可以有多个元素，大大提升查找效率，这就是为什么数据库索引用的就是B+树，因为索引很大，不可能都放在内存中，所以通常是以索引文件的形式放在磁盘上，所以当查找数据的时候就会有磁盘I/O的消耗，而B+树正可以解决这种问题，减少与磁盘的交互，因为进行一次I/O操作可以得到很多数据，增大查找数据的命中率。
这就可以很明显的看出B+树的优势：
- 单个节点可以存储更多的数据，减少I/O的次数。
- 查找性能更稳定，因为都是要查找到叶子结点。
- 叶子结点形成了有序链表，便于查询。
8、索引的性能分析和优化
如果系统中发现慢 SQL 或者性能影响业务的 sql，可以通过 EXPLAIN 来判断 SQL 的执行计划。
查看执行计划会有如下信息：
关于 key_len 长度计算公式：
也就是说索引 key_len 长度过大，也会影响 SQL 性能。所以为什么也不能默认 null，会占用字节，索引长度哟。
索引提高 SQL 效率的方法
- 利用索引加快查询速度
- 行记录检索
- 从索引记录中直接返回结果（联合索引）
9、索引使用规则
联合索引(last_name, first_name, gener)
一，全值匹配
查询语句where条件和索引中的所有列进行匹配。
1 SELECT * FROM people WHERE last_name='zhang' AND first_name='yin' AND gender='m';
二，最左前缀匹配
查询条件可以匹配索引的最左若干列。注意关键词”最左前缀“。
--可以使用部分索引"last_name"
SELECT * FROM people WHERE last_name='zhang' AND gender='m';
--无法使用索引
SELECT * FROM people WHERE first_name='zhang' AND gender='m';
三，列前缀匹配
查询中的like条件，在有些场景下也可以使用索引。如 last_name like 'zh%'可以使用索引，而last_name like '%ing'则无法使用索引。
--可以使用索引，因为BTREE的节点比较key值时是从key值得最左侧开始匹配
SELECT * FROM people WHERE last_name like 'zhang%' AND gender='m' ;
四，范围查询
索引的列也支持范围查询。范围字段会结束索引对范围后面索引字段的使用
SELECT * FROM people WHERE last_name > 'zhang' AND last_name
五，排序
ORDER BY语句在特定情况下也支持用索引来排序来提高性能。
EXPLAIN SELECT * FROM people WHERE last_name = 'zhang' ORDER BY first_name ASC
ASC 升序 DESC降序
六，限制
1，查询列不能参与表达式运算，否则无法使用索引。
--表设计中没有age列，以示参考--假设age是索引中一部分，这样的查询将无法使用到索引
SELECT * FROM people WHERE last_name='zhang' AND age+3>28;
--这样写就可以使用索引
SELECT * FROM people WHERE last_name='zhang' AND age>25;
2，如果不是从索引的最左列开始，则无法使用索引。如，根据first_name、gender或者查找的查询无法使用索引。
--不是从last_name开始匹配，所以无法使用索引
SELECT * FROM people WHERE first_name='zhang' AND gender='m'
3，不能跳过索引中的列。
--不能跳过first_name查询，否则只有last_name列用到了索引
SELECT * FROM people WHERE last_name='zhang' AND gender='m'
4，如果查询中某个列是范围查询(like，between，>）
--由于first_name用了like查询，所以gender列无法使用索引了
SELECT * FROM people WHERE last_name='zhang' AND first_name LIKE '%in' AND gender='m';
七、不走索引
1.Like就是%在前面的不走索引，在后面的走索引
2.用索引列进行计算的，不走索引
3.对索引列用函数了，不走索引
4. 索引列用了!= 不走索引 ，mysql在使用不等于（！=或者<>）的时候无法使用索引会导致全表扫描
5.is null,is not null 也无法使用索引
10、QA
Q：为什么不是一般二叉树？
A：如果二叉树特殊化为一个链表，相当于全表扫描。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。
Q：为什么不是平衡二叉树呢？
A：我们知道，在内存比在磁盘的数据，查询效率快得多。如果树这种数据结构作为索引，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，但是平衡二叉树可是每个节点只存储一个键值和数据的，如果是B树，可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就降下来啦，查询效率就快啦。
Q：索引的树型数据结构为什么使用B+树，而非B树？
A：1）B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。innodb中页的默认大小是16KB，如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。
2）B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，链表连着的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。
3）B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出。另外MySQL中的显示的B树就是B+树。
Q：为什么常用B+ Tree而非Hash作为索引类型？
A：数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。
Q：索引的一些潜规则
A：覆盖索引，回表，索引数据结构（B+树），最左前缀原则，索引下推
注：
1.哈希索引数据并不是按照索引列的值顺序存储的，故无法用于排序
2.哈希索引只支持等值比较查询，如：=、in()、<=>(安全比较运算符，用来做 NULL 值的关系运算)，不支持任何范围查询