数据库索引的本质是一种数据结构。
索引是定义在数据表的基础之上的，包括某个表中一列或若干列值，以及指向相对应数据页的逻辑指针。
建立索引的意义，在于能够通过缩小一张表中需要查询的记录/行的数目，来加快搜索所需数据的速度。
相当于图书的目录，可根据目录的页码快速找到所需内容。
一个好的数据库表设计，从一开始就应考虑添加索引。
因为索引数据的存储是有序的，通过查询索引数据去找东西，不需要遍历所有记录；最极端情况也就是：索引查询的效率等于二分法查询，趋近于
优缺点
索引最大的优点，是能够大大加快数据的检索速度。这是创建索引的最主要原因。
- 通过创建唯一性索引，可保证数据库表中每一行数据的唯一性
- 可加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义
对应的，索引的缺点也不少：
- 每创建出来一个索引，就是一个具体的数据结构，占用磁盘的固定的物理空间，聚簇索引的空间就更大了
- 创建索引和维护索引需要耗费时间，随着数据量增加而增加
- 对表中的数据进行增加、删除和修改时，索引也要动态维护：由此会降低维护速度
因此建立索引需要遵循以下原则：
设计原则
- 对于经常查询的字段，建议创建索引
- 索引不是越多越好：大量索引不仅会占用磁盘空间，而且影响对数据表 insert，delete，update 等语句的性能
- 所以：避免对经常增删改的表进行过多的索引，因为表中数据被更改的同时，索引也会进行调整和更新，十分消耗系统资源
- 数据量小的表建议不要创建索引：少于万级、十万级别的就不需要建立索引了，此时索引不仅起不到明显的优化效果，对于索引结构的维护反而消耗系统资源
- 不要在区分度低（表的数据重复，分布平均）的字段建立索引：如性别字段，只有“男”“女”，建索引完全起不到优化效果
- 当唯一性是某字段本身的特征时，指定唯一索引能提高查询字段
- 在频繁进行排列分组（group by / order by）的列上建立索引，如待排序有多个，可在这些列上建立联合索引。
联合索引为什么香
对列 col1、col2 和 col3 建立联合索引：
1 | KEY test_col1_col2_col3 on test(col1,col2,col3); |
如上，联合索引 test_col1_col2_col3 实际上建立了 (col1) (col1,col2) 和 (col1,col2,col3) 三个索引，对于大量数据的表，使用联合索引会大大减少开销；
同时就联合索引对数据进行搜索时，数据库可以直接遍历索引获取数据，无需回表，减少了很多 IO 操作；
另外，索引列越多，通过索引筛选出来的数据就越少，大大提升效率；但这并不意味着索引多就一定好，毕竟索引越多，占据的硬盘空间就越大，过多索引反而会影响 IO 性能。
一般联合索引不超过 3 列，否则虽然减少回表操作，但是索引块过多，查询时遍历的开销也会加大。
最左前缀匹配原则
指的是最左优先，在搜索数据的时候从联合索引的最左边开始匹配。
再比如，就联合索引 test_col1_col2_col3，执行下面这个查询语句：
1 | SELECT * FROM test WHERE col1="1" AND col2="2" AND col4="4"; |
执行搜索的时候会根据最左前缀匹配原则（col1 在最左，col2 次之，col3 在最右），使用索引 (col1,col2) 进行数据匹配。
如果 SQL 语句只按照 col2 或 col3 进行查询，那么查询不会使用这个联合索引。
这是因为数据库在建立索引时会将索引按照列的顺序进行排序，而查询时必须按照索引声明时列的顺序依次查询。因此，只有在查询中按照索引最左边的列开始进行查询时，才能利用到这个索引。如果查询中没有按照索引最左边的列开始查询，那么即使这个索引存在，也不会被使用。
如果查询时候使用的条件是
1 | col2="1" AND col1="2" |
优化器会自动优化为匹配联合索引的顺序，此时同样能命中索引。
最左匹配原则的应用可以提高查询效率，特别是当数据库中有大量数据时，能减少数据库系统的负载。因此，在设计复合索引时，要考虑到查询中最常用的条件，将这些条件放在索引的最左边，可以使得查询效率更高。
注：
联合索引的连接类型 type 值的不同，会对联合索引的最终搜索结果有影响：
type = ref：非唯一性索引扫描，返回匹配某个单独值的所有行；type = index：从索引第一个字段逐个查找，直到找到符合的某一个索引；连接类型为该值时，说明此时不符合最左前缀匹配原则，与其无关。
因此在建立索引的时候，应该尽量将区分度高的字段放前面，尽量减少一条 SQL 语句的影响行数。
实现
一般采用 B 树作为索引的实现。
为什么不使用 Hash 搜索呢？
Hash 的查询、插入、修改、删除的平均时间为
对于单行查询的需求，Hash 索引更快；但 SQL 的应用场景多为排序（order by）、分组（group by）和比较大小等操作，如果仍然使用 Hash，时间会退化为
所以根据 SQL 的需求，索引一般设计为树的数据结构；而且因为数据库存储大量数据的关系，一般使用 m 叉（m > 2，即 2-3 树）自平衡二叉搜索树的实现方式。
MySQL 采用 B+ 树作为 InnoDB 引擎的数据结构。
对于范围查询，B+ Tree 比 B-Tree 的优势更大：
- 适合磁盘存储，能充分利用局部性原理和磁盘预读
- 很低的树高度（扁平化），能存储大量数据
- 索引本身占用内存小
- 能很好支持单点查询、范围查询（无需中序回溯）、有序性查询。