索引的出现其实就是为了提高数据查询的效率,就像目录一样
索引模型
- 提高读写效率的数据结构,哈希表、有序数组、搜索树
哈希表是以key-value存储数据结构, 哈希的思路:把值放在数组里,用一个哈希函数将key换算成一个确定位置,然后把value放在数组的这个位置。 ( 1.这个地方有个把key计算成确定的位置，最初是取余数，把余数相同的放到同一位置，这个位置叫做哈希槽。 2.哈希槽相同的key就会产生哈希碰撞，碰撞后就会挂在同一链表上。 3.查找的时候先通过key找到哈希槽，再遍历链表找到对应key匹配的值。就像字典，造字典的人会把相同声母的字放一起，字的拼音就是key，声母就是哈希槽。查字典先根据拼音声母查到具体位置，再去挨个儿找key（拼音）直到找到字。 )
MySQL中的哈希索引并不适用于所有类型的数据。
-
它通常试用于等值查询分为单条多条查询,与等值查询对应的是模糊查询、范围查询。
-
有序数组在等值查询和范围查询场景你各种功能的性能非常优秀。
-
内存连续 -> 数组中的元素在内存中是连续存储的,这种连续性使得CPU可以预取数据, CPU可以提前加载接下来的元素到缓存中。这种预取操作提高了缓存的利用率，因为相邻的数据很可能很快就会被访问。
-
高速缓存映射 -> 直相连映射就是内存中每个数据块映射到高速缓存中的位置是固定的，一段连续的内存加载到高速缓存中的位置也必定是连续的，如果是非连续的内存地址在取数据时内存的片选线会将地址转发走，如果相邻数据在内存中不同存储页中这个查询成本会比较高。直相连映射方式内存使用率低、查询效率高、方式简单一般使用在最靠近CUP的那一级缓存中，离CUP越远内存使用率就越重要所以最远端比如内存用的就是全相连映射（每个磁盘上地址都可以映射到内存地址上任意一个），中间就是使用折中方式组相连映射。所以有序数组是因为有一段连续的内存地址映射在高速缓存中提高CPU查询效率，才在等值跟范围查询中性能优秀的原因。
- 有序数组索引只适用于静态存储索引。
搜索树
- 二叉树是搜索效率最高的,但是实际上大多数数据库存储并不使用二叉树。 原因: 消耗磁盘IO
为什么数据库存储使用B+树而不是二叉树
- 因为二叉树树高过高，每次查询都需要访问过多节点，即访问数据块过多，而从磁盘随机读取数据块过于耗时。
MYSQL的存储结构
单位: 表>段>区>页>行 在数据库中,不论读一行还是多行,都将这些行所在的页进行加载。所以存储空间的基本单位是页。 一页->一个节点在B+树,数据库I/O操作的最小单位是页，与数据库相关的内容都会存储在页的结构里。
B+树索引结构
在一棵B+树中，每个节点为都是一个页，每次新建节点的时候，就会申请一个页空间
同一层的节点为之间，通过页的结构构成了一个双向链表
非叶子节点为，包括了多个索引行，每个索引行里存储索引键和指向下一层页面的指针 叶子节点为，存储了关键字和行记录，在节点内部(也就是页结构的内部)记录之间是一个单向的表
B+树页节点的特点和检索过程
页主要作用是存储记录,在页中记录以单链表的形式进行存储。单链表优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。因此页目录中提供了二分查找的方式，来提高记录的检索效率。
从B+树的根开始，逐层找到叶子节点。找到叶子节点为对应的数据页，将数据叶加载到内存中，通过页目录的槽采用二分查找的方式先找到一个粗略的记录分组。在分组中通过链表遍历的方式进行记录的查找
B+树索引
数据库访问数据要通过页,一个页就是一个B+树节点,访问一个节点相当于一次IO操作,所以越早查询到越好。
MyISAM和INNODB模型 B+树实现方式不同
MyISAM存储引擎中的索引是基于B+树实现的，其中叶节点的data域存储的是数据记录的磁盘地址。索引检索过程如下： 通过B+树搜索算法查找指定的键（Key）。 如果找到该键，取出叶节点data域中的值，这个值是数据记录在磁盘上的地址。 根据这个地址，直接读取数据文件中相应位置的数据记录。
InnoDB的数据文件本身就是索引文件。这棵树的叶节点data域保存了完整的数据记录。InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。
基于主键索引和普通索引的查询有什么区别
- 主键索引的叶子节点是整行数据
- 非主键索引的叶子节点内容是主键的值
如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
索引维护
B+树为了维护索引有序性,在插入新值的时候需要做必要的维护。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。 有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：只有一个索引；该索引必须是唯一索引。你一定看出来了，这就是典型的 KV 场景。由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。
比如有个身份信息表，业务上就两个字段，身份证号（唯一）和信息(长文本字段，不适合建立索引)，然后业务上也只会根据身份证号来查询这个表。那么应该直接用身份证号做主键，分析如下 （1）自增主键：那么根据身份证号字段索引查到id，又根据id回表去查到信息。 （2）身份证号作为主键：直接根据主键找就能找到信息，相比方案1中要查询两颗树的成本更小。
这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。