1、索引的常见类型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。这里介绍三种常见可以提高读写效率的数据结构，分别是哈希表、有序数组和搜索树。

哈希表：

是一种以键-值（key-value）存储数据的结构，通过key找到对应的value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。

优点是查询效率高，缺点是无法排序。

所以，哈希表这种结构适用于只有等值查询的场景，比如Memcached 及其他一些NoSQL引擎。

有序数组：

在等值查询和范围查询场景中的性能都非常优秀，但是在更新数据的时候就比较麻烦，因为在中间插入一条记录就必须得挪动后面所有的记录，成本太高。

因此，有序数组索引只适用于静态存储引擎

搜索树：

二叉搜索树是比较经典的数据结构，二叉搜索树父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值。查询时间复杂度为O(log(N))，为了保证平衡，防止退化成链表结构，更新的时间复杂度也是O(log(N))

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。虽然二叉树搜索效率最高，但实际上大多数的数据库存储并不使用二叉树。因为索引不止存在内存中，还要写到磁盘中。如果采用二叉树就会导致树的高度过高，每次查询都需要多次读取磁盘，比较耗时。

为了减少读磁盘，让查询过程访问尽量少的数据库块，我们一般使用“N叉”树，“N”取决于数据块的大小。

以InnoDB 的一个整数字段索引为例，这个N差不多是1200。MySQL默认一个节点的大小为16K，一个整数（bigint）字段索引的长度为8B，每个索引还要6B指向其子树的指针，故 16kb/14b ≈ 1200。

如果树高为4，就可以存1200的3次方个值，差不多17亿数据。树根的数据块总是在内存中，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实，书的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。至于第三层数据，按全量计算，1200*1200*16kb ≈ 23G。

N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

2、InnoDB索引引擎

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB使用了B+树索引模型，数据都是存储在B+树中。

每一个索引在InnoDB里面对应一颗B+树，一张表可以有多个索引，也就是可以对应多颗索引树。

假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引。

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))
engine=InnoDB;

mysql>insert into T(id,k) values(100,1),(200,2),(300,3),(500,5),(600,6);

两颗树的示意图如下：