索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本数课书的目录部分，通过目录中找到对应文章的页码，便可快速定位到需要的文章。MySQL中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记录，直到找到与条件符合的记录。
如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查找数据，这样操作非常消耗时间。如果数据顺序摆放，那么也需要从1到6行按顺序读取，这样就相当于进行了6次IO操作，依旧非常耗时。如果不借助任何索引结构帮助快速定位数据的话，我们查找col 2=89这条记录，就要逐行去查找、去比较。从Col 2= 34开始，进行比较，发现不是，继续下一行。我们当前的表只有不到10行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多次6盘I/O才能找到。现在要查找Col 2=89这条记录。CPU必须先去磁盘查找这条记录，找到之后加载到内存，再对数据进行处理。这个过程最耗时间的就是磁盘I/O(涉及到磁盘的旋转时间（速度较快)、磁头的寻道时间(速度慢、费时))
假如给数据使用二叉树这样的数据结构进行存储，如下图所示
对字段Col 2添加了索引，就相当于在硬盘上为Col 2维护了一个索引的数据结构，即这个二叉搜索树。二叉搜索树的每个结点存储的是<K，V>结构，key 是Col 2, value是该key所在行的文件指针〈地址)。比如:该二叉搜索树的根节点就是(34,0x07)。现在对Col 2添加了索引，这时再去查找Col 2=89这条记录的时候会先去查找该二叉搜索树（二叉树的遍历查找)。读34到内存，89>34;继续右侧数据，读89到内存，89 == 89;找到数据返回。找到之后就根据当前结点的value快速定位到要查找的记录对应的地址。可以发现，只需要查找两次就可以定位到记录的地址，查询速真就提高了。
这就是为什么要建索引，目的就是 为了减少磁盘I/0的次数，加快查询速率
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。
这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现 高级查找算法 。
（1）类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本 ，这也是创建索引最主要的原因。
（2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
（3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。
增加索引也有许多不利的方面，主要表现在如下几个方面： （1）创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
因此，选择使用索引时，需要综合考虑索引的优点和缺点。
先来看一个精确匹配的例子：
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
以主键为搜索条件
可以在页目录中使用二分法快速定位到对应的值，然后再遍历该值对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件
因为在数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的值。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能 从第一个页 沿着 双向链表 一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是 超级耗时 的。如果一个表有一亿条记录呢？此时 索引 应运而生。
建一个表：
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键，这个表使用 Compact 行格式来实际存储记录的。这里我们简化了index_demo表的行格式示意图：
我们只在示意图里展示记录的这几个部分：
将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
把一些记录放到页里的示意图就是：
我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们 想快速的定位到需要查找的记录在哪些数据页 中该咋办？我们可以为快速定位记录所在的数据页而 建立一个目录 ，建这个目录必须完成下边这些事：
下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。给所有的页建立一个目录项。
至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为 索引 。
我们把前边使用到的目录项放到数据页中的样子就是这样：
从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调 目录项记录和普通的 用户记录 的
不同点：
目录项记录 的 record_type 值是1，而 普通用户记录 的 record_type 值是0。主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含 很多列 ，另外还有InnoDB自己添加的隐藏列。min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。相同点：两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。
虽然说 目录项记录 中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有 16KB 大小，能存放的 目录项纪录 也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的 目录项记录，如何处理呢？
这里我们假设一个存储目录项记录的页 最多只能存放4条目录项纪录，所以如果此时我们再向图中插入一条主键值为 230 的用户记录的话，那就需要分配一个新的存储 目录项纪录 的页：
从图中可以看出，我们插入了一条主键值为320的用户记录之后需要两个新的数据页：
页31 。页30的容量已满 （我们前边假设只能存储4条目录项记录），所以不得不需要一个新的 页32 来存放 页31 对应的目录项。现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步
骤，以查找主键值为 20 的记录为例：
目录项记录页页30 和 页32 ，又因为页30表示的目录项的主键值的范围是 [1, 320) ，页32表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在 页30 中。目录项记录 的页中通过主键值定位一条目录项记录的方式说过了。问题来了，在这个查询步骤的第1步中我们需要定位存储目录项纪录的页，但是这些 页是不连续的，如果我们表中的数据非常多则会 产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？那就为这些存储目录项记录再生成一个 更高级的目录，就像一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：
如图，我们生成了一个存储更高级目录项的 页33 ，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在 [1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值 不小于320 的话，就到页32中查找更详细的目录项记录。
我们可以用下边这个图来描述它：
这个数据结构，它的名称是 B+树 。
一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页 最多存放3条记录 ，存放目录项记录的页 最多存放4条记录 。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存放 1000条目录项记录 ，那么：
100 条记录。1000×100=10,0000 条记录。1000×1000×100=1,0000,0000 条记录。1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！！！你的表里能存放 100000000000 条记录吗？所以一般情况下，我们 用到的B+树都不会超过4层 ，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过 二分法 实现快速定位记录。
B+树的层次越低，IO的次数就越少，时间就节省很多
索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。
聚簇索引就是针对主键搭建起来的B+树
聚簇索引 并不是一种单独的索引类型，而是 一种数据存储方式（所有的用户记录都存储在了叶子节点），也就是说所谓的**索引即数据，数据即索引**
术语 “聚簇” 表示数据行和相邻的键值放在连续的逻辑块上
特点：
单向链表 。用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。叶子节点 存储的是完整的用户记录。聚簇索引，所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处。这种聚簇索引并不需要我们在MySOL语句中显式的使用 INDEX 语句去创建，InnoDB 存储引警会 自动 的为我们创建聚簇索引。优点：
数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快排序查找 和 范围查找 速度非常快节省了大量的io操作 。缺点：
限制：
上边介绍的 聚簇索引 只能在搜索条件是 主键值 时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该怎么办呢?肯定不能是从头到尾沿着链表依次遍历记录一遍。
答案：我们可以 多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用 c2 列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示：
这个B+树与上边介绍的聚簇索引有几处不同:
单向链表。用户记录的页 也是根据页中记录的c2列大小顺序排成一个 双向链表。目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个 双向链表。c2列+主键 这两个列的值。主键+页号 的搭配，而变成了 c2列+页号 的搭配。所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了。以查找c2列的值为4 的记录为例，查找过程如下：
目录项记录页。根页面，也就是 页44，可以快速定位到 目录项记录 所在的页为页42 (因为2 < 4 < 9)。目录项记录 页确定用户记录真实所在的页。页42 中可以快速定位到实际存储用户记录的页，但是由于c2 列并没有唯一性约束，所以c2 列值为4的记录可能分布在多个数据页中，又因为2 < 4 <= 4，所以确定实际存储用户记录的页在页34和页35 中。c2和c1 (也就是主键两个列，所以我们必须再根据主键值a去聚簇索引中再查找一遍完整的用户记录。概念：回表
我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根
据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就
是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！
问题： 为什么我们还需要一次 回表 操作呢？直接把完整的用户记录放到叶子节点不OK吗？
回答：
如果把完整的用户记录放到叶子节点是可以不用回表。但是 太占地方了，相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了
因为这种按照 非主键列 建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引 (英文名 secondary index)，或者 辅助索引。由于我们使用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树是为c2列建立的索引。
非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引。
小结： 聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别：
叶子节点 存储的就是我们的 数据记录，非聚簇索引的叶子节点存储的是 数据位置。:非聚簇索引不会影响数据表的物理存储顺序。只能有一个聚索引，因为只能有一种排序存储的方式，但可以有 多个非聚索引，也就是多个索引2目录提供数据检索。查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低。我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照 c2和c3列 的大小进行排序，这个包含两层含义：
注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
联合索引只会建立如上图一样的1棵B+树。
如图所示，我们需要注意以下几点：
目录项记录 都由 c2、c3、页号 这三个部分组成，各条记录先按照C2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。叶子节点 处的用户记录由 c2、c3和主键c1列 组成。注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
我们前边介绍B+索引的时候，为了大家理解上的方便，先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，实际上B+树的形成过程是这样的：
这个过程特别注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。
我们知道B+树索引的内节点中目录项记录的内容是索引列+页号的搭配，但是这个搭配对于二级索引来说有点不严谨。还拿index_demo表为例，假设这个表中的数据是这样的：
| c1 | c2 | c3 |
|---|---|---|
| 1 | 1 | ‘u’ |
| 3 | 1 | ‘d’ |
| 5 | 1 | ‘y’ |
| 7 | 1 | ‘a’ |
如果二级索引中目录项的内容只是索引号+页号的搭配的话，那么为c2列建立索引后的B+树应该长这样：
如果我们想要新插入一行记录，其中c1、c2、c3的值分别是：9、1、c，那么在修改这个为c2列建立的二级索引对应的B+树时便碰到了个大问题：由于页3中存储的目录项记录是由c2列+页号的值构成的，页3中的两条目录项记录对应的c2列的值都是1，那么我们这条新插入的记录到底应该放在页4中，还是应该放在页5中啊？答案是：对不起，懵了。
为了让新插入记录能找到自己在哪个页里，我们需要 保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。 所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：
也就是我们把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，所以我们为c2列建立二级索引后的示意图实际上应该是这样子的：
这样我们再插入记录(9, 1, ‘c’)时，由于页3中存储的目录项记录是由c2列+主键+页号的值构成的，可以先把新记录的c2列的值和页3中各目录项记录的c2列的值作比较，如果c2列的值相同的话，可以接着比较主键值，因为B+树同一层中不同目录项记录的c2列+主键的值肯定是不一样的，所以最后肯定能定位唯一的一条目录项记录，在本例中最后确定新记录应该被插入到页5中。
一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错！这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问的存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢？那就是目录层级非常非常非常多，而且最后的那个存放真实数据的目录中存放一条记录。费了半天劲只能存放一条真实的用户记录？所以InnoDB的一个数据页至少可以存放两条记录。
B树索引适用存储引擎如表所示：
| 索引/存储引擎 | MyISAM | InnoDB | Memory |
|---|---|---|---|
| B-Tree索引 | 支持 | 支持 | 支持 |
即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是Btree索引；而Memory默认的索引是Hash索引。
MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。
下图是MyISAM索引的原理图。
我们知道 InnoDB 中索引即数据，也就是聚族索引的那棵B+树的叶子节点中已经把所有完整的用户记录都包含了而 MyISAM 的索引方案虽然也使用树形结构，但是却 将索引和数据分开存储：
没有刻意按照主键大小排序，所以我们并不能在这些数据上使用二分法进行查找MVISAM存储引擎的表会把索引信息另外存储到一个称为索引文件 的另一个文件中。MISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是 主键值 + 数据记录地址的组合。
MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主键索引和二级索引 Secondary key)在结构上没有任何区别，只是主键索引要求key是唯一的，而二级索引的key可以重复。如果我们在C2上建立一个二级索引，则此索引的结构如下图所示：
MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：
① 在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。
② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
③ InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ InnoDB要求表必须有主键（MyISAM可以没有）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助。比如:
举例1: 知道了InnoDB的索引实现后，就很容易明白 为什么不建议使用过长的字段作为主键，因为所有二级索引都引用主键索引，过长的主键索引会令二级索引变得过大。
举例2: 用非单调的字段作为主键在innoDB中不是个好主意，因为lnnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用 自增字段作为主键则是一个很好的选择。
索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：
空间上的代价时间上的代价一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。为了能建立又好又少的索引，我们得学学这些索引在哪些条件下起作用的。
从MySQL的角度讲，不得不考虑一个现实问题就是磁盘IO。如果我们能让索引的数据结构尽量减少硬盘的I/O 操作，所消耗的时间也就越小。可以说，磁盘的 I/O 操作次数 对索引的使用效率至关重要。
查找都是索引操作，一般来说索引非常大，尤其是关系型数据库，当数据量比较大的时候，索引的大小有可能个G甚至更多，为了减少索引在内存的占用，数据库索引是存储在外部磁盘上的。当我们利用索引查询的时候不可能把整个索引全部加载到内存，只能逐一加载 ，那么MySQL衡量查询效率的标准就是磁盘10次数。
略
Hash 本身是一个函数，又被称为散列函数，它可以帮助我们大幅提升检索数据的效率。
Hash 算法是通过某种确定性的算法(比如 MD5、SHA1、SHA2、SHA3) 将输入转变为输出。相同的输入永远可以得到相同的输出，假设输入内容有微小偏差，在输出中通常会有不同的结果。
举例:如果你想要验证两个文件是否相同，那么你不需要把两份文件直接拿来比对，只需要让对方把 Hash 函数计算得到的结果告诉你即可，然后在本地同样对文件进行 Hash 函数的运算，最后通过比较这两个 Hash 函数的结果是否相同，就可以知道这两个文件是否相同。
加速查找速度的数据结构，常见的有两类：
(1)树，例如平衡二又搜索树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N)；
(2)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1)；
采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+ 树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次I/O 操作，从效率来说 Hash 比 B+ 树更快。
在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[o…m-1]的槽位上。
上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：
实验：体会数组和hash表的查找方面的效率区别
// 算法复杂度为 O(n)
@Test
public void test1() {
int[] arr = new int[100000];
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
long start = System.currentTimeMillis();
for (int j = 1; j <= 100000; j++) {
int temp = j;
for (int i = 0; i < arr.length; i++) {
if (temp == arr[i]) {
break;
}
}
}
long end = System.currentTimeMillis();
System.out.println("time： " + (end - start)); // time： 823
}
// 算法复杂度为 O(1)
@Test
public void test2() {
HashSet<Integer> set = new HashSet<>(100000);
for (int i = 0; i < 100000; i++) {
set.add(i + 1);
}
long start = System.currentTimeMillis();
for (int j = 1; j <= 100000; j++) {
int temp = j;
boolean contains = set.contains(temp);
}
long end = System.currentTimeMillis();
System.out.println("time： " + (end - start)); // time： 5
}
Hash结构效率高，那为什么索引结构要设计成树型呢？
原因1: Hash 索引仅能满足() ()和N 查询。如果进行 范围查询，哈希型的索引，时间复杂度会退化为o(n);而树型的“有序”特性，依然能够保持o(log2N) 的高效率。
原因2: Hash 索引还有一个缺陷，数据的存储是 没有顺序的，在ORDER BY 的情况下，使用 Hash 索引还需要对数据重新排序。
原因3: 对于联合索引的情况，Hash 值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询。
原因4:对于等值查询来说，通常 Hash 索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。
Hash索引适用存储引擎如表所示：
| 索引 / 存储引擎 | MyISAM | InnoDB | Memory |
|---|---|---|---|
| HASH | 索引 | 不支持 | 不支持 |
Hash索引的适用性：
Hash 索引存在着很多限制，相比之下在数据库中 B+ 树索引的使用面会更广，不过也有一些场景采用 Hash 索引效率更高，比如在键值型 (Key-Value) 数据库中，Redis 存储的核心就是 Hash 表。
MySQL中的 Memory 存储引擎支持 Hash 存储，如果我们需要用到查询的临时表时，就可以选择 Memory 存储引擎，把某个字段设置为 Hash 索引，比如字符串类型的字段，进行 Hash 计算之后长度可以缩短到几个字节。当字段的重复度低，而且经常需要进行 等值查询 的时候，采用 Hash 索引是个不错的选择。
另外，InnoDB 本身不支持 Hash 索引，但是提供自适应 Hash 索引 (Adaptive Hash lndex)。什么情况下才会使用自适应 Hash 索引呢?如果某个数据经常被访问，当满足一定条件的时候，就会将这个数据页的地址存放到Hash 表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。这样让 B+ 树也具备了 Hash 索引的优点。
采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。
我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：
mysql> show variables like '%adaptive_hash_index';
如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。
1. 二叉搜索树的特点
2. 查找规则
我们先来看下最基础的二叉搜索树 (Binary Search Tree)，搜索某个节点和插入节点的规则一样，我们假设搜索插入的数值为 key：
但是存在特殊的情况，就是有时候二叉树的深度非常大。比如我们给出的数据顺序是5,22,23,34,77,89,91)，创造出来的二分搜索树如下图所示：
上面第二棵树也属于二分查找树，但是性能上已经退化成了一条链表，查找数据的时间复杂度变成了 O(n)。你能看出来第一个树的深度是3，也就是说最多只需 3 次比较，就可以找到节点，而第二个树的深度是7，最多需要7次比较才能找到节点。
为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。
为了解决上面二叉查找树退化成链表的问题，人们提出了 平衡二叉搜索树(Balanced Binary Tree)，又称为AVL树(有别于AVL算法)，它在二叉搜索树的基础上增加了约束，具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
这里说一下，常见的平衡二叉树有很多种，包括了 平衡二叉搜索树 、 红黑树、数堆、伸展树。平衡二又搜索树是最早提出来的自平衡二又搜索树，当我们提到平衡二叉树时一般指的就是平衡二又搜索树。事实上，第一棵树就属于平衡二又搜索树，搜索时间复杂度就是 O(log2N)。
数据查询的时间主要依赖于磁盘 I/O 的次数，如果我们采用二叉的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是 o(log2n)，当 n 比较大时，深度也是比较高的，比如下图的情况：
每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5次 /0 操作。虽然平衡二又树的效率高，但是树的深度也同样高，这就意味着磁盘/0 操作次数多，会影响整体数据查询的效率。
针对同样的数据，如果我们把二叉树改成 M 叉树 (M>2) 呢？当 M=3 时，同样的31个节点可以由下面的三叉树来进行存储：
你能看到此时树的高度降低了，当数据量 N 大的时候，以及树的分叉数 M 大的时候，M 又树的高度会远小于二又树的高度(M >2)。所以，我们需要把 树从“瘦高”变“矮胖”。
B 树的英文是 Balance Tree，也就是 多路平衡查找树。简写为B-Tree (注意横表示这两个单词连起来的意思，不是减号)。它的高度远小于平衡二叉树的高度。
B 树的结构如下图所示：
B 树作为多路平衡查找树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x 个关键字，那么指针数就是 x+1。对于一个 100 阶的 B树来说，如果有 3 层的话最多可以存储约 100 万的索引数据。对于大量的索引数据来说，采用 B 树的结构是非常适合的，因为树的高度要远小于二叉树的高度。
一个 M 阶的 B 树（M>2）有以下的特性：
根节点的儿子数的范围是 [2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为[ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i] <Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …,P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]指向关键字大于 Key[k-1] 的子树。
所有叶子节点位于同一层。
上面那张图所表示的 B 树就是一棵 3 阶的 B 树。我们可以看下磁盘块 2，里面的关键字为（8，12），它有 3 个孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小于 8，(9，10) 在 8 和 12 之间，而 (13，15)大于 12，刚好符合刚才我们给出的特征。
然后我们来看下如何用 B 树进行查找。假设我们想要查找的关键字是 9，那么步骤可以分为以下几步：
我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。
你能看出来在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素。B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，IO次数足够少，就可以提高查询性能。
小结：
再举例1：
B+树也是一种多路搜索树，基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式，比如 MySQL。相比
于B-Tree，B+Tree适合文件索引系统。
B+ 树和 B 树的差异：
下图就是一棵 B+树，阶数为3，根节点中的关键字 1、18、35分别是子节点(1，8，14)，(18，24，31)和(35，41，53)中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中，因此在叶子节点中包括了所有的关键字信息，并且每一个叶子节点都有一个指向下一个节点的指针，这样就形成了一个链表。
比如，我们想要查找关键字 16，B+ 会自顶向下逐层进行查找：
整个过程一共进行了3次 I/O 操作，看起来 B+ 和 B 的查询过程差不多，但是 B+ 和 有个根本的差异在于，B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢?
首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
其次，B+ 树的查询效率更高。这是因为通常 B+ 树比 B 树 更矮胖 (阶数更大，深度更低)，查询所需要的磁盘 l/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。
不仅是对单个关键字的查询上，在查询范围上，B+ 树的效率也比 B 高。这是因为所有关键字都出现在 B+ 树的叶子节点中，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找。而在 B树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。
B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。
但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。
思考题:为了减少IO，索引树会一次性加载吗?
1、数据库索引是存储在磁盘上的，如果数据量很大，必然导致索引的大小也会很大，超过几个G。
2、当我们利用索引查询时候，是不可能将全部几个G的索引都加载进内存的，我们能做的只能是：逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点。
思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT(占用4个字节)或BIGINT(占用8个字节)，指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值，因为是估算，为了方便计算，这里的K取值为10^3也就是说一个深度为3的B+Tree索引可以维护 103 * 103 * 103 = 10亿条记录。（这里假定一个数据页也存储10^3条行记录数据了）
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~ 4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？
1.B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2、B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的节点，而只是叶子结点中关键字的索引。所有任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
思考题：Hash索引与B+树索引的区别
1、Hash索引不能进行范围查询，而B+树可以。这是因为Hash索引指向的数据是无序的，而B+树的叶子节点是个有序的链表。
2、Hash索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用），而B+树可以。对于联合索引来说，Hash索引在计算Hash值的时候是将索引键合并后再一起计算Hash值，所以不会针对每个索引单独计算Hash值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。
3、Hash索引不支持 ORDER BY 排序，因为Hash索引指向的数据是无序的，因此无法起到排序优化的作用，而B+树索引数据是有序的，可以起到对该字段ORDER BY 排序优化的作用。同理，我们也无法用Hash索引进行模糊查询，而B+树使用LIKE进行模糊查询的时候，LIKE后面后模糊查询（比如%结尾）的话就可以起到优化作用。
4、InnoDB不支持哈希索引
思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？
如果使用的是 MySQL 的话，我们需要了解 MySQL 的存储引擎都支持哪些索结构，如下图所示(参考来源https://dev.mysql.com/doc/refman/8.0/en/create-index.html) 。如果是其他的 DBMS，可以参考相关的DBMS文档。
你能看到，针对InnoDB和MyISAM 存储引擎，都会默认采用B+ 树索引，无法使用Hash 索引。InnoDB提供的自适应 Hash 是不需要手动指定的。如果是 Memory/Heap 和NDB 存储引擎，是可以进行选择 Hash 索引的。
R-Tree在MySQL很少使用，仅支持 geometry数据类型 ，支持该类型的存储引擎只有myisam、bdb、
innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果
没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记
录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满
足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度
地图这种超大数据库中，这种方法便必定不可行了。R树就很好的 解决了这种高维空间搜索问题 。它把B
树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解
结点的方法，保证树的平衡性。因此，R树就是一棵用来 存储高维数据的平衡树 。相对于B-Tree，R-Tree
的优势在于范围查找。
| 索引 / 存储引擎 | MyISAM | InnoDB | Memory |
|---|---|---|---|
| R-Tree索引 | 支持 | 支持 | 不支持 |
使用索引可以帮助我们从海量的数据中快速定位想要查找的数据，不过索引也存在一些不足，比如占用存储空间、降低数据库写操作的性能等，如果有多个索引还会增加索引选择的时间。当我们使用索引时，需要平衡索引的利(提升查询效率)和 (维护索引所需的代价)。
在实际工作中，我们还需要基于需求和数据本身的分布情况来确定是否使用索引，尽管 索引不是万能的，但 数据量大的时候不使用索引是不可想象的，毕竟索引的本质，是帮助我们提升数据检索的效率。
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在
于选择合适算法和改进算法。
