- 索引是 存储引擎 用于快速找到记录的一种 数据结构。
- 当表中的数据量越来越大时，索引对性能的影响愈发重要
- 索引优化应该是对查询性能优化最有效的手段了，有时能使查询性能提高几个数量级
索引基础
MySQL中，存储引擎用类似的方法使用索引：
- 先在索引中找到对应值
- 根据匹配的索引记录找到对应的行
- 索引可以包含一个或多个列的值
- 索引多个列的情况，MySQL应用最左原则
- 创建一个包含两个列的索引 != 创建两个单列的索引
索引的类型
- MySQL中，索引是在存储引擎层实现的
- 并不是所有的存储引擎都支持所有类型的索引
- 多个存储引擎支持的同一种类型索引，实现方式也可能不同
B-Tree索引
- 谈论索引时，如果没有指明类型，多半说的是B-Tree索引，大多数MySQL存储引擎都支持这种索引
- 使用B-Tree数据结构来存储数据
- InnoDB使用的B+Tree，按原数据格式进行存储， InnoDB根据主键引用被索引的行
- MyISAM使用前缀压缩技术使索引更小， MyISAM索引通过数据的物理位置--> 被索引的行
- 索引列的顺序很重要
B-Tree索引加速访问数据的原因
B+Tree
- 存储引擎不需要进行全表扫描获取数据，从索引的根节点进行搜索
- 根节点的槽中存放了指向子节点的指针
- 通过比较节点页的值和要查找的值可以找到合适的子节点指针
- 叶子节点的指针指向被索引的数据
- 最终存储引擎要么找到对应的值，要么记录不存在
- 树的深度和表的大小直接相关
- B-Tree对索引列是顺序组织存储的，适合范围数据查找
- 索引对多个值进行排序的依据是create table时定义索引 列的顺序
B-Tree索引适用范围
create table People (
last_name varchar(50) not null,
first_name varchar(50) not null,
birth date not null,
gender enum('m', 'f') not null,
key (last_name, first_name, birth)
);
- 索引中的包含了last_name, first_name, birth 的值
-
全值匹配
利用索引中全部的列（last_name, first_name, birth ）进行查询 -
匹配最左前缀
只使用第一列（last_name ）查询 -
匹配列前缀
全部 last_name以‘J'开头的查询 -
匹配范围值
last_name 在'a'和 'k'之间的查询（只用到索引第一列last_name） - 精确匹配某一列并范围匹配另一列
last_name=’Allen‘ 并且first_name以'K' 开头的查询（索引 last_name, first_name） - 只访问索引的查询
覆盖索引（只访问索引列的查询，如查询last_name='Allen', first_name='Kim'的birth）
- 索引树中的节点是有序的，可用于查询中的ORDER BY 操作（满足上1-6）
B-Tree索引限制
- 若不是按索引的最左列开始查找，则无法使用索引
- 类似的，也无法使用索引查询last_name以某个字母结尾的人
- 不能跳过索引的列（last_name, birth 只能用到last_name的索引）
- 查询中某列含范围查询，则右边所有的列都无法使用索引优化查询
- where last_name='abc' and first_name like 'z%' and birth = '1999'
- 这个查询只能用索引的前两列，因为like是一个范围查询
- 如果查询列的数量有限，可以用多个等于条件代替范围查询
索引列的顺序很重要
哈希索引
- 哈希索引（hash - index）基于哈希表实现
- 只有精确匹配索引所有列的查询才会有效
- 对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash-code）
- 哈希码是一个较小的值，并且不同键值的行计算出的哈希码也不一样
- 哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针
- MySQL中，只有Memory引擎显示支持哈希索引（也是Memory默认索引类型），Memory引擎同时也支持B-Tree索引。Memory索引支持非唯一哈希索引，如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中
- InnoDB引擎有一种特殊的功能叫“自适应哈希索引”。当InnoDB注意到某些索引值被引用得很频繁时，他会在内存中基于B-Tree索引智商在创建一个哈希索引。---- 完全自动、内部的行为、用户无法控制或配置
- 哈希索引结构十分进奏，查找速度非常快
哈希索引限制
- 哈希索引不存储字段值。不能使用-索引覆盖查询-
- 哈希索引数据并不是按索引值顺序存储的，无法用于排序
- 哈希索引总是使用索隐列的全部内容计算哈希值，如在（a,b）上穿件索引，查询只有a列无法使用索引
- 哈希索引只支持等值比较查询= 和 in()，不支持范围查询如where price> 20
- 哈希冲突很多的列建立哈希索引，更新删除时引擎需遍历对应哈希表中的每一行，找到并删除或修改，代价很大
伪哈希索引（例）
- 情景：需要存储大量的URL，并且需要根据url进行搜索查找。如果使用B-Tree来存储URL，存储的内容就会很大，因为URL本身都很长
create table url (
id int unsigned not null auto_increment,
url varchar(255) not null,
primary key(id)
);
在数据量增多的情况下，下面的查询会很慢
mysql> SELECT id FROM url where url = 'http://www.mysql.com";
- 解决方案：
alter table url add url_crc int unsigned not null default 0;
在新加的url_crc列上加索引，查询时采用
select id from url where url ='www.mysql.com' and url_crc = CRC32('www.mysql.com');
- 解决方案缺陷 & 措施：
- 缺陷1： 只支持精确查找
- 缺陷2：需要维护哈希值
- 缺陷2解决方案： 手动维护 OR 触发器
创建触发器
-- 插入时
delimiter //
create trigger url_crc_ins BEFORE insert on url for each row BEGIN set NEW.url_crc=crc32(NEW.url);
END;
//
-- 更新时
create trigger url_crc_upd BEFORE update on url for each row BEGIN set NEW.url_crc=crc32(NEW.url);
END;
//
delimiter;
- 不要使用SHA1() 和MD5()作为哈希函数，因为这两个函数计算出来的哈希值是非常常的字符串，也会浪费大量空间，比较时也会更慢。SHA1()和MD5()是强加密函数，设计目标是最大限度消除冲突，在这里并不需要这样高的要求
- 如果表数据非常大，crc32()函数会出现大量的哈希冲突
- 注意：当使用哈希索引进行查询时，必须在where子句中包含常量值
聚簇索引
- 聚簇索引并 不是一种单独的索引类型，而是一种 存储数据的方式
- 在高性能的索引策略中作笔记
空间数据索引（R-Tree）
- MyISAM表支持空间索引，可用作地理数据存储
- 空间索引会从所有唯独索引数据，无需前缀查询
- GIS 的解决方案比较好的是PostgreSQL的PostGIS
全文索引
- 全文索引是一种特殊类型的索引，查找的是文本中的关键字，而非直接比较索引中的值
- 全文索引和其他索引的匹配方式完全不一样
- 全文索搜索类似于搜索引擎做的事情么不是简单的where条件匹配
- 在同一列同时创建全文索引和基于值的B-Tree索引不会有冲突
其他索引
- 第三方存储引擎TokuDB使用分形树索引（fractal tree index），是一种较新开发的数据结构
- 大多数情况下针对InnoDB的讨论也使用与TokuDB
