索引

素引(在 MYSQL中也叫做“键（key)”)是存储引擎用于快速找到记录的一种数据结构。

类似一本书的“索引”部分（目录），可以快速找到某个特定的主题。


索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降——是骡子是马，拉出来溜溜。

索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将査询性能提高几个数量级，“最优”的素引有时比一个“好的”索引性能要好两个数量级。创建一个真正“最优”的索引经常需要重写査询。

  • 索引是在存储引擎层实现，不是在服务器层实现。

查询过程

  1. 在索引中查询对应的值，不再需要走全表扫描。
  2. 根据匹配的索引记录（1v1,1vN）找到对应的数据行。
  3. 进行后续的过滤、查询、展示

示意图：

查询 索引 数据行
3 |———> 5 lili
actor_id = 5 ———> 5 —-+———> 5 gaoming
2 2 dadong

索引优点

  1. 减少服务器需要扫描的数据量；
  2. 避免排序和临时表；
  3. 将随机I/O变为顺序I/O；

是最佳解决方案吗

  • 对于数据量较小的表，大部分情况是不需要创建索引，全表扫描更高效。不推荐
  • 对于数据量中到大型表（1kw之内），非常有效，推荐创建索引。
  • 对于特大型的表，索引代价更为明显（cud 都需要更新索引数据），可以使用 分区 技术。不推荐

索引类型

B-Tree

意味着所有的值都是按顺序存储的，并且每个叶子页到根的距离相同。

支持有效的查询类型

  • （1）全值匹配：和索引中的所有列进行匹配；
  • （2）匹配最左前缀：如当索引有多列时，只使用索引的第一列；
  • （3）匹配列前缀：只使用索引第一列的值的开头部分；
  • （4）匹配范围值：只使用索引的第一列；
  • （5）精确匹配某一列，并范围匹配另一列：只使用索引的第一列及第二列的开头部分；
  • （6）只访问索引的查询：查询只需要访问索引，而无须访问数据行，即覆盖索引；
  • （7）可用于对上述 6种查询类型的 ORDER BY查询；

索引覆盖：返回的所有列都包含在索引列里。 index_student_age (‘student_id’,’age’) select student_id,age from table where student_id = 1 and age = 1

B-Tree索引的限制：

  • （1）如果不是按照索引的最左列开始查找，则无法使用索引；
  • （2）不能跳过索引中的列；
  • （3）如果查询中有某个列的范围查询（包括LIKE等），则其右边所有列都无法使用索引优化查找；

无效的查询类型

  • 非最左前缀：idx_a_b, where b =1 无效，最左列未指定
  • 非最左前列值：idx_a_b where a like ‘%test’ 无效 最左列值为确定
  • 不可以跳列：idx_a_b_c, where a=1 and c =1 只能使用 a 列表索引，后续是全数据扫描。
  • 某列范围查询：idx_a_b_c, where a=1 and b like ‘b%’ and c =1 只能使用 a,b列索引，c 列所有用不了。

列范围查询优化（对于值可枚举的话）
idx_a_b_c, where a=1 and b like ‘b%’ and c =1 可优化为 where a =1 and ((b = b1 and c =1) or (b =b2 and c =1))

使用方式不同

索引数据：

  • MyISAM：使用前缀压缩技术使得索引（数据量）更小
  • InnoDB：按照原数据格式进行存储（意味着体积更大）。

索引关联对应的数据库行：

  • MyISAM：通过数据的物理位置引用
  • InnoDB：通过主键引用

哈希索引

哈希索引( hash index)基于哈希表实现，只有精确匹配索引所有列的查询才有效。

对于每一行数据，存储引檠都会对所有的素引列计算一个哈希码( hash code),哈希码是个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针

在 MYSQL中，只有 Memory 引擎显式支持哈希索引。这也是 Memory引擎表的默认索引类型， Memory引擎同时也支持B-Tree索引。值得一提的是， Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

支持有效的查询类型

  • （1）全值匹配：和索引中的所有列进行匹配；查询速度非常快。

哈希索引的限制：

  • 无法用于排序：原理于hash值为乱序存储
  • 不支持部分索引匹配查找（不支持最左前缀列）：idx_a_b_c, where a=1 and b吧 =1 用不上索引。
  • 不支持索引覆盖：哈希索引表中只有哈希值和行指针，没有存储列数据，无法免读行数据（对应内存表影响不大）。
  • 只支持等值比较查询：包括 = IN() <=> 不支持范围查询。
  • 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引繁必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选
  • 择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎翯要遍历对应哈希值的链表中的每一行，找到并刷除对应行的引用，冲突越多代价越大。

InnoDB有一个特殊的功能：自适应哈希索引，当InnoDB注意到某些索引值被使用得非常频繁时，就会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。

伪哈希索引

使用与值较长的列表，通过信息摘要算法计算出固定长度的值。

  1. where url = 'http:...........';
  2. where url_crc = crc32(url);
  4. crate table t_name (
  5.     id int unsigned not null auto_increment,
  6.   url varchar(255) not null,
  7.   url_crc int unsigned not null default 0,    -- 索引列
  8.   primary key(id),
  9.   key idx_crc ('url_crc')  -- 索引列
  10. )
  12. -- 通过触发器解决 url_crc 值更新的问题
  14. DELIMITER //
  16. CREATE TRIGGER table_crc_ins BEFORE INSERT ON t_name FOR EACH ROW BEGIN -- 新增行处理
  17. SET NEW.url_crc = crc32(NEW.URL);
  18. END;
  20. CREATE TRIGGER table_crc_upd BEFORE UPDATE ON t_name FOR EACH ROW BEGIN -- 更新行处理
  21. SET NEW.url_crc = crc32(NEW.URL);
  22. END;
  24. DELIMITER;

如果采用这种方式，记住不要使用SHA1（）和D5（）作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。SHA1（）和MD5（）是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围，同时又能够提供更好的性能。

哈希列冲突解决方法
哈希值有一定的概率是重复的，所以查询是需要带上真实值进行过滤。
where url = 'http://...' and url_crc = crc32('http://......')

还可以使用如FNV64（）函数作为哈希函数，这是移植自 Percona Server的函数，可以以插件的方式在任何 MYSQL版本中使用，哈希值为64位，速度快，且冲突比CRC32（）要少很多。

空间数据索引（R-Tree）

MyISAM表支持空间索引，可以用作地理数据存储。

全文索引

查找的是文本中的关键词，而不是直接比较索引中的值。适用于MATCH AGAINST操作，而不是普通的WHERE条件操作。