从SQL Server到MySql(4): MySql中的索引

1 索引基础

• 索引的原理
  • 减少定位记录时所经历的中间过程, 从而加快存取速度.
  • 一般来说,索引本身也很大, 不可能全部存储在内存中, 因此索引往往以索引文件的方式存储在硬盘上. 这样, 索引查找过程中会产生磁盘I/O消耗.
  • 评价索引的数据结构的指标: 查找过程中磁盘I/O操作次数的渐进复杂度.
• 索引的"三星系统"
  • 一星: 索引将相关的记录放到一起.
  • 二星: 索引中的数据顺序和查找中的排序顺序一致
  • 三星: 索引中的列包含了查询中需要的全部列.
• 索引的优点
  • 减少了服务器需要扫描的数据量. (索引存储了实际的列值).
  • 避免排序和临时表. (按照顺序存储数据).
  • 将随机I/O变为顺序I/O. (顺序存储).
• MySQL 中的索引
  • 在存储引擎层实现的, 所以没有统一的索引标准.
  • MYSql 不能将过滤条件传到存储引擎层.

2 B-Tree 索引

2.1 B-Tree 索引

• 所有的值按照顺序存储的, 每个叶子页到根的距离相同.
  • 数据库将一个node的大小设置为一个页的大小. 每个node 只需一次I/O就可以完全载入.
  • 同时, 把B-Tree中的m值设置的非常大, 从而降低了树的高度, 有利于一次完全载入.
• 索引对多个值进行排序的�依据是定义索引时的顺序.
• 适用于全键值, 键值范围, 匹配最左前缀, 匹配列前缀, 只访问索引的查询.
  • 还可用于查询中的Order by 操作.

2.2 m-way 查找树

• 每个节点的键值数小于m.
• 每个节点的度(子树的数目)小于等于m.
• 键值按顺序排列.
• 子树的键值要完全小于(左树)或大于(右树)或介于父节点之间(中间树)的键值.

2.3 限制. 索引的顺序是非常重要的.

• 不是按照索引的最左列开始查找,则无法使用索引.
• 不能跳过索引中的列(�例如使用3个列做索引, 然后按1,3列进行查询).
• 若查询中有某个列的范围查询, 则其右边的所有列都无法使用索引来优化查询.

3 哈希索引

3.1 哈希索引

• 只有精确匹配索引所有列的查询才有效.
• 只有Memory引擎显式支持(非唯一)哈希索引.
• InnoDB 会在某些索引值被频繁使用时, 在内在基于B-Tree之上再创建哈希索引, 单这是完全自动,内部的行为. 用户无法控制.
• 适合: "星型"schema,需要关联很多查找表.

3.2 限制

• 哈希索引只包含哈希值和行指针,而不存储字段值. 所以不能避免行读取.
• 数据不是按照索引值顺序存储的, 也就无法用于排序.
• 不支持部分索引列匹配查找. 使用的是全部索引列的内容计算的哈希值.
• 只支持等值比较查找,而不支持任何范围查询.
• 遇到哈希冲突时, 需要遍历链表中所有的行指针, 逐行比较,知道找到所有符合条件的行.
• 若果哈希冲突很多, 那么索引维护操作的代价也会很高.

3.3 创建自定义哈希索引

• 在B-Tree基础上创建一个伪哈希索引.
• 还是使用B-Tree进行查询, 但使用哈希值而不是键本身进行索引查找.
• 在查询的Where 条件中手动指定使用的哈希函数.
• 缺陷是需要维护哈希值, 可以手动维护, 也可以使用触发器.
• 使用CRC32(), 在数据表非常大时,会出现大量的冲突,可以自实现一个64位(返回整数的)哈希函数.
• SHA1(),MD5()的设计目标是最大限度消除冲突, 所以会产生非常长的字符串,浪费空间.
• 由于"生日悖论",出现哈希冲突的概率的增长速度比想象的要快很多.
• 要避免冲突, 必须在where条件中带入哈希值和对应的值
  • where crc=CRC32('gun') and word = 'gnu'.

4 索引即数据结构

• 每种查找算法都只能应用于特定的数据结构之上.
  • 数据本身的组织结构不可能完全满足各种数据结构.
  • 索引是数据结构.
  • B+ Tree: 内节点不存储数据, 只存储key; 叶子节点不存储指针.
    • 每个节点的指针上线为2d.
  • 磁盘预读的长度一般为页(page)的整数倍.
    • 主存和硬盘以页为单位交换数据.
    • 将tree 中一个节点的大小设置为一个页的大小.
    • B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）.