5.1.1 索引的类型

B-Tree 索引

应该就是指 BTree 索引.

底层存储引擎可能使用不同的存储结构:

  • NDB: T-Tree
  • InnoDB: B+Tree

image.png

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

DDL:

image.png

索引图示:

  • 图中给的例子好像有些问题, 索引没有按照 DDL 顺序排序

image.png

可以使用 B-Tree 索引的查询类型:

  • 全值匹配, 和索引中的所有列进行匹配 (索引的所有列都参与匹配)
  • 匹配最左前缀, 只使用索引的第一列
  • 匹配列前缀, 匹配某一列的值的开头部分
  • 匹配范围值
  • 精确匹配某一列并范围匹配另外一列
  • 只访问索引的查询, 覆盖索引

B-Tree 的限制:

  • 如果不是按照索引的最左列开始查找, 则无法使用索引
  • 不能跳过索引中的列
  • 如果查询中有某个列的范围查询, 则其右边所有列都无法使用索引

哈希索引

只有精确匹配索引所有列的查询才有效.

Memory 引擎默认使用哈希索引:

  • 也支持 B-Tree
  • 支持非唯一哈希索引 (拉链法)

DDL:

image.png

数据:

image.png

假想的哈希函数 f():

image.png

哈希索引示意图:

image.png

哈希索引的限制:

image.png
image.png

NDB 支持唯一哈希索引.

InnoDB, 自适应哈希索引:

image.png

伪哈希索引:

  • 新增对某列的 hash 列 (如 crc32), 并建立 B-Tree 索引, 查询使用如下方法

image.png

使用触发器自动维护 crc 列:

  1. DDL

image.png

  1. 创建触发器

image.png

  1. 验证

image.png

  • 不要使用 SHA1() 和 MD5(), 因为 hash 结果太长, 同时也慢

使用 MD5 返回值的一部分作为自定义哈希函数:

image.png

空间数据索引 (R-Tree)

image.png

全文索引

  • 停用词
  • 词干
  • 复数
  • 布尔搜索

其他索引类别

  • TokuDB, 分形树索引, fractal tree index
  • ScaleDB, Patricia tries