1. B-Tree 索引

B-Tree 索引的结构如下，每个所引节点包含了索引值、数据库整行数据、子节点的指针。索引树上的值都是按照索引列顺序排好的。

1. B-Tree 索引上每个节点都存储了对应数据库的整行数据，B+Tree只在叶子节点存放了整行数据，B-Tree索引查询时，查询出某一值时不一定到叶子节点，只要在树上任何节点查询到对应的值，直接就能拿到整行数据。而B+Tree查询出某一行数据一定得查询到叶子节点。

2. B-Tree 索引能够加快访问数据的速度，因为存储引擎不需要再进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。

3. B-Tree 对索引列是顺序存储的，所以很适合查找范围数据。

4. B-Tree 通常可以支持 “只访问索引的查询”，即查询只需要访问索引，而无需访问数据行。这称为覆盖索引。

5. B-Tree 根节点到每个叶子节点的高度都一样。

6. B-Tree  索引的限制：

先建个表：

CREATE TABLE `mine_user` (
  `id` varchar(32) NOT NULL,
  `age` int(11) DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  `sex` int(11) DEFAULT NULL,
  `url` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `union_index` (`age`,`name`,`sex`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

1. 如果不是按照索引的最左列开始查找，则无法使用索引。例如上表联合索引union_index：查询的时候，如果要按照 name或者按照 sex字段查询或者 name = 1 and sex = 1，这样的查询是使用不到索引的。也无法查找 name 字段中以某个字结尾的人。

2. 不能跳过索引中的列来查询，即 age = 12 and sex = 1 中间跳过了 name 字段，这样查询联合索引是使用不到的，只是用到了第一列的索引。

3. 如果查询中某个列有范围查询，那么联合索引失效。如：age = 12 and name like 'ee%' and sex = 1 这样查询时，那么是范围查找，只能只使用到前两列的索引。

2.B+Tree 索引

先通过下图认识一下B+Tree的大致结构。B+Tree 是由二叉树、二叉平衡树演变而来的。因为树的高度和io次数有关，为了保持树高，B+Tree对二叉平衡树进行了改造。每个索引节点包含索引值、子节点指针。叶子节点包含数据库整行数据。索引树上的索引值都是按照索引列顺序排好的，叶子节点也是按照顺序排好的。

 Mysql中的InnoDB存储引擎默认使用的是 B+Tree 索引。B+Tree 索引整个树形结构上存储的是主键索引值，并且这些值都是按照排好的顺序存储在上面的，一般称树形上的节点为索引页，索引页上的每个索引数据为索引节点，最底层的是叶子节点，叶子节点是以页为单位的，每个页里面存储了mysql中的n行数据，能存多少行主要看每行数据占用内存的大小了，mysql中默认每页的容量大小是16kb。

叶子节点中的页与页以双向指针连接。每个页中的行数据也是以双向指针连接起来的。从上图看似这些行数据是物理内存连续的，其实这些数据只是逻辑连续，物理内存不连续的。

B+Tree 索引分为聚集索引和非聚集索引。主键索引存储的索引结构为聚集索引，其它普通索引存储的索引结构为非聚集索引。

聚集索引：聚集索引的叶子节点存储了数据库整行的数据，根据主键查询数据时，经过几次io加载了叶子节点的数据页时，能够直接得到整行数据值。聚集索引的索引值和数据库的整行数据在同一个树形结构上。

非聚集索引：非聚集索引又称辅助索引，它与主键索引最主要的区别是：非聚集索引的叶子节点只包含索引值和主键值。所以根据普通索引查询时，先根据索引列查询到主键值，然后再根据主键值去主键索引树上查询整行值，性能肯定比主键索引查询慢一点。

3. 哈希索引

哈希索引是基于哈希表实现的，只有精确查询时索引才会有效。在Mysql中只有Memory存储引擎是显示支持哈希索引的，Memory存储引擎默认的索引就是哈希索引。

原理：

插入数据：在一个表的一列上加一个哈希索引后，在插入一条记录时，这个字段会先通过hash函数计算出一个hash值放到hash表中，再把这条记录存储到磁盘上，hash表中只会存这个字段值的hash值和指向这条记录的指针。

查询数据：通过hash索引列这个字段查询查询时，先通过hash函数计算出这个字段的hash值，然后在hash表中根据计算出的hash值查询出对应的记录指针，很快的能精确查询出需要的结果。数据量大后，会出现hash冲突，所以添加hash索引后，hash表底层会把冲突的记录的指针以链表的方式存储到同一个hash条目中，查询的时候，把指针链表返回，用字面值去比较匹配指针指向的记录结果里的查询列字段值，直到查询出所有需要的结果为止。

hash索引的限制：

1. hash索引只包含hash值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。但是hash索引查询速度非常快，对性能不会有很大影响。

2. hash索引数据并不是按照索引值顺序排序的，所以也就无法用于排序。

3. hash索引不支持部分索引列匹配查找，因为hash索引始终是使用索引列的全部内容来计算hash值的。如：在 name、sex这两个字段上加hash索引，那么就不支持 name 索引查询，也不支持 sex 索引查询。因为hash函数计算的 name 的hash值和 sex 的hash值分别与 name、sex联合计算的hash值不匹配。

4. hash索引只支持等值比较查询。包括 = 、in 。不支持范围hash索引查找。

5. 访问hash索引的数据非常快，如果当hash冲突很多的时候，是比较影响hash索引的访问速度的。当出现hash冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的值。

6. 如果hash索引冲突比较多的时候，维护索引的操作开销比较大。如删除一行值，这个值恰好hash冲突比较多，指针在链表中维护，如果删除这一行，那么存储引擎避免不了链表的遍历匹配，然后删除，而链表的遍历匹配的开销是比较大的。

InnoDB 引擎有一个特殊的功能叫做 自适应哈希索引。当 InnoDB 注意到某些索引值被引用的比较频繁时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这样让 B-Tree 索引也具有哈希索引的一些优点。这是一个完全自动的、内部的行为，用户无法感知，也无法去控制或配置，但是这个功能可以关闭。

我们可以直接在 InnoDB 中直接使用哈希索引：

可以通过navicat设计表时，选择索引的类型：

我们也可以在 B-Tree 上使用伪哈希索引：

新建个表：

CREATE TABLE `web` (
  `id` varchar(32) NOT NULL,
  `web_name` varchar(32) DEFAULT NULL,
  `url` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `url_index` (`url`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

其实使用的还是 B-Tree 索引，只是索引的列从想要索引的列替换为一个hash函数计算的结果值的列上加 B-Tree 索引。

举个例子：如果数据库中有一个字段存的值都是比较长的，如存 url，如果在这个url上直接加索引，那么对这个字段加加索引后对应的 B-Tree 体积就比较大，且查询相对比较慢，因为在这个索引上二分查找时也是比较整个字符串来查询结果的，维护这个索引的时候也是需要比较匹配的。这个时候可以删除这个字段上的索引，增加一列 hash 值。然后对这个列加 B-Tree索引。

修改上表为下

CREATE TABLE `web` (
  `id` varchar(32) NOT NULL,
  `web_name` varchar(32) DEFAULT NULL,
  `url` varchar(255) DEFAULT NULL,
  `hash_url` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `hash_url_index` (`hash_url`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

如：

select * from web where url = "https://www.wewe.com/sd/ddd?e=1" ; 

修改为：

select * from web where url = "https://www.wewe.com/sd/ddd?e=1"  and  hash_url = CRC32(https://www.wewe.com/sd/ddd?e=1);

如上查询的时候，mysql优化器会使用这个选择性很高而体积很小的基于 hash_url 列的索引来完成查询。如果查询到的 hash_url 有多个，那么再使用 url 字段这个值在基于 hash_url 查询的结果集中逐一去匹配。

如果是这样查询：select * from web where  hash_url = CRC32(https://www.wewe.com/sd/ddd?e=1);  那么查询的结果有多条时（hash冲突），不能确定哪条结果是需要的。CRC32() 为hash函数。

 4. 全文索引

全文索引是一种特殊类型的索引，它查找的是文本中的关键词，而不是直接比较索引中的值。全文索引和其它类型的索引的匹配方式完全不一样。全文索引更类似于搜索引擎做的事，而不是简单的 where 条件匹配。在相同列上可以同时创建全文索引和B-Tree索引，不会有冲突，全文索引使用于 MATCH AGAINST 操作，而不是普通的where条件操作。

#创建索引
alter table web add FULLTEXT KEY(url);

#全文查询
select * from web where MATCH(url) AGAINST ('codinglabs.org');