索引的目的就是为了提高查询效率
索引常见模型
哈希表
一种以键-值存储数据的结构
优点：
- 插入速度快
缺点： - 哈希索引做区间查询的速度很慢
结论： - 这种结构适用于只有等值查询的场景，比如memcached及其他一些NoSql引擎
有序数组
有序的数组结构
优点：
- 等值查询(二分查找)和范围查询场景中性能优秀
缺点： - 插入速度慢、成本高
结论： - 这种结构适用于静态存储引擎
搜索树
一种节点的左儿子小于父节点，父节点又小于右儿子的结构
优点：
- 查询、更新效率高，为O(log(N))
缺点： - 索引不止在内存中，还要写在磁盘上。二叉搜索树的索引层次高，会产生高成本的磁盘IO。
结论 - 为了让一个查询尽量少地读磁盘，必须让查询过程访问经量少的数据库(尽量少的进行磁盘IO)。一般用N叉树，InnoDB的N在1200左右。
N叉搜索树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
其他模型
- 跳表
- LSM树
InnoDB的索引模型
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。
InnoDB索引组织结构
图中左边为主键索引，右边为非主键索引
- 主键索引的叶子节点存的是整行数据。在InnoDB里也被成为聚簇索引
- 非主键索引的叶子结点存的是主键的值。在InnoDB里也被称为二级索引
这里引入一个问题：基于主键索引和普通索引的查询有什么区别？
1 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
2 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
结论：基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
索引维护
- B+树为了维护索引有序性，在插入新值时需要做必要的维护。增加数据可能会出现页分裂。删除数据可能出现分裂过程的逆过程。
这里引入另一个问题：哪些场景下应该使用自增主键，而哪些场景下不应该
1 自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
2 没有其他索引时，使用业务的唯一字段作为主键。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小.
面试
1.“N叉树”的N值在MySQL中是可以被人工调整的么？
- 通过改变key值来调整
N叉树中非叶子节点存放的是索引信息，索引包含Key和Point指针。Point指针固定为6个字节，假如Key为10个字节，那么单个索引就是16个字节。如果B+树中页大小为16K，那么一个页就可以存储1024个索引，此时N就等于1024。我们通过改变Key的大小，就可以改变N的值 - 改变页的大小
页越大，一页存放的索引就越多，N就越大。
2.innodb B+树主键索引的叶子节点存的是什么
- B+树的叶子节点是page （页），一个页里面可以存多个行
