阅读完需：约 11 分钟
为什么需要索引
总体来说，索引是为了提高查询速度的，当数据量比较大时，从头到尾依次检索是无法接受的。另外，存储的数据会包含多个属性来描述业务实体，属性可以连续或分开存储，分别对应到MySQL和HBase。
以MySQL为例，学生这个实体有学号、姓名、性别、所属班级等属性，一般还有个主键ID，现在有个需求：查询学号为002的学生姓名。
数据是存储在磁盘上的，操作系统读取磁盘的最小单位是块，如果没有索引，会加载所有的数据到内存，依次进行检索，加载的总数据会很多，磁盘IO多。
如果有了索引，会以学号为key创建索引，MySQL采用B+树结构存储，一方面加载的数据只有学号和主键ID，另一方便采用了多叉平衡树，定位到指定学号会很快，根据关联的ID可以快速定位到对应行的数据，所以检索的速度会很快，因为加载的总数据很少，磁盘IO少。
可见，索引可以大大减少检索数据的范围、减少磁盘IO，使查询速度很快，因为磁盘IO是很慢的，是由它的硬件结构决定的。
下面，再详细介绍下磁盘存储结构和数据定位过程，加深对索引的理解。
硬盘存储结构
磁盘内部结构如下：
- 很多个盘片被串在一个主轴上，主轴带着他们快速的旋转；
- 每个盘片都有很多一圈一圈的磁道，每个磁道又分为一个一个的扇区；
- 多个盘片上的同一位置的磁道组成了一个柱面；
- 每个盘片上都有可以读写数据的磁头；
访问数据时，可以说：把1柱面，1磁头，1扇区的数据取出来？
磁盘会把1磁头挪到1柱面，就是对应的磁道， 这叫“寻道时间”，然后再旋转磁盘，让磁头指向1扇区，开始读取数据，这叫“旋转时间”，转速快的硬盘能更快的旋转到特定扇区，所以性能会更好。
结构比较复杂，但操作系统给封装了，提供了一个叫做逻辑块的方式，你看到磁盘就是有一个个“块”组成的，编号为1, 2, 3, ..n，把指定的块转化成柱面，磁头，扇区， 按照上面说的方法寻道，旋转，读取数据。
为了方便我们操作，操作系统又进一步抽象，抽象成了文件，由文件系统去保存和读取数据，我们只需要与文件打交道，文件使用inode结构，通过它可以轻松的找到这个文件所使用的所有磁盘块。
扇区是对硬盘而言，块是对文件系统而言，块是文件存取的最小单位，一般一个块由连续的几个扇区组成。
一个表的数据块以链表的方式串联在一起，数据以行为单位一行一行的存放在磁盘的块中。
数据定位过程
以MySQL的B+树为例，简单说下几种常见场景下，数据的定位过程。
第一种场景：索引精确查找
select * from user_info where id = 23 ;
确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过 二分查找找到记录或未命中。
第二种场景：索引范围查找
select * from user_info where id >= 18 and id < 22 ;
读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点, 顺序扫描所有结果, 直到终止条件满足id >=22。
第三种场景：全表扫描
select * from user_info where name = 'abc' ;
直接读取叶节点头结点， 顺序扫描， 返回符合条件记录， 到最终节点结束
第四中场景：二级索引查找
create table table_x(int id primary key, varchar(64) name , key sec_index(name) ) ;
select * from table_x where name = 'd' ;通过二级索引查出对应主键，拿主键回表查主键索引得到数据， 二级索引可筛选掉大量无效记录，提高效率
索引的类别
上面介绍了索引的优点和数据的定位过程，对其有了整体了解，另外，索引有不同种类和不同的实现方式，这节重点梳理下这些概念。
聚簇索引与非聚簇索引
简单来说，聚集索引是一种索引组织形式，索引的键值逻辑顺序决定了表数据行的物理存储顺序，而非聚集索引则就是普通索引了，仅仅只是对数据列创建相应的索引，不影响整个表的物理存储顺序。
聚簇索引的优点有：
- 范围查询效率更高；
- 特别适合有一小部分热点数据频繁读写的场景；
- 通过主键访问数据时快速可达；
InnoDB引擎是聚集索引组织表，它的聚集索引选择规则是这样的：
- 首先选择显式定义的主键索引做为聚集索引；
- 如果没有，则选择第一个不允许NULL的唯一索引；
- 还是没有的话，就采用InnoDB引擎内置的ROWID作为聚集索引；
主键索引和辅助索引
主键索引，简称主键，由一个或多个列组成，用于唯一性标识数据表中的某一条记录。
InnoDB数据表的主键设计通常遵循几个原则：
- 采用一个没有业务用途的自增属性列作为主键；
- 主键字段值总是不更新，只有新增或者删除两种操作；
- 不选择会动态更新的类型，比如当前时间戳等；
辅助索引，常规所指的索引，也叫二级索引，又分为唯一索引和非唯一索引。
InnoDB引擎中，主键索引会被选中作为聚集索引，而唯一索引和普通辅助索引间除了唯一性约束外，在存储上没本质区别。
MySQL索引演化
本小节主要介绍索引是如何根据需求一步步演变最终成为B+树结构，基本思路是减少访问数据的总量，相应的减少磁盘IO。
密集索引（Dense Index ）
根据减少无效数据访问的原则，我们将键的值拿过来存放到独立的块中。并且为每一个键值添加一个指针， 指向原来的数据块。
当进行定位操作时，不再进行表扫描。而是进行索引扫描(Index Scan)，依次读出所有的索引块，进行键值的匹配，这样带来的问题是需要很多空间来存储Dense索引。另外索引的定位效率也比较低，可以通过排序和查找算法来减少IO的访问。
假设一个块中能存储100行数据，10,000,000行的数据需要100,000个块的存储空间。假设键值列（+指针）占用一行数据1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储空间换来了大约全表扫描10倍的定位效率。
折半块查找
需要对Dense进行索引，每个索引块内是有序的，另外，需要一个数组按顺序存储索引块地址，这样整体就有序了，数组也要存储到磁盘上，放在单独的块链中。
折半查找的时间复杂度是O(log2(N))，在上面的列子中，dense索引总共有10,000个块。假设1个块能存储2000个指针，需要5个块来存储这个数组。通过折半块查找，我们最多只需要读取5（数组块）+ 14（索引块log 2(10000)）+1（数据块）=20个块。
从图中可以看到，相对于密集索引，编号是有序的。
稀疏索引（Sparse Index）
介绍基于块的折半查找时发现，读出每个块后只需要和第一行的键值匹配，就可以决定下一个块的位置（方向）。 因此有效数据是每个块的第一行数据，将每一个块的第一行的数据单独拿出来，和索引数组的地址放到一起。这样就可以直接在这个数组上进行折半查找了，这个数组就进化成了Sparse Index了。
需要10个块来存储10000个Dense Index块的地址和首行键值，通过Sparse索引，仅需要读取10(Sparse块)+1(Dense块)+1(数据块)=12个块。
多层稀疏索引
因为Sparse Index本身是有序的，所以可以为Sparse Index再建sparse Index。通过这个方法，一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块为止。
这个例子中，Sparse Index只有10个块，只需要再建立一个Sparse Index.通过两层Sparse Index和一层Dense Index查找时，只需读取1+1+1+1=4个块。
如果数据本身是基于某个Key来排序的，那么可以直接在数据上建立sparse索引，而不需要建立一个dense索引层(可以认为数据就是dense索引层)，这就是说的聚集索引。
B+树
由于键值是有序的，因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表的方式进行连接， 就可以实现高效的范围查找。如下图所示：
这就是我们常说的B+ Tree，倒过来看下：
最后总结下它的特点：
- 每次进行定位操作时，都从根开始查找；
- 每层索引只需要读出一个块；
- 最底层的Dense Index或数据称作叶子(leaf)；
- 每次查找都必须要搜索到叶子节点，才能定位到数据；
- 索引的层数称作索引树的高度(height)；
- 索引的IO性能和索引树的高度密切相关，索引树越高，磁盘IO越多；
- 进行范围查找时，效率很高；
