索引

索引是一种由原数据生成的具有特殊数据结构的数据，根据其特殊的结构，在某方面（如查找）会比无序的数据更有优势

B+ Tree

结构

• B Tree + 叶子节点的顺序访问指针

操作

• 查找

  • 从根节点开始，递归地二分查找

• 插入

  • 插入操作后会破坏二叉树的平衡性
  • 通过分裂、合并、旋转来维护平衡性

B+ Tree VS 红黑树

• B+ Tree树的高度更低
• 磁盘寻道的次数与树高成正比，所以红黑树更耗时
• 磁盘的预读不进行寻道

使用的条件

小的表使用全局扫描更有效

中大型的表索引非常有效

特大型的表，建立和维护索引的代价很大

分类

B+ Tree索引

• 地位

  • MySQL大多数存储引擎的默认索引类型

• 特点

  • 无需全表扫描，只需搜索树
  • B+ Tree有序，可以查找、排序、分组

• InnoDB

  • 主索引

    • 叶子节点存储数据

  • 辅助索引

    • 叶子节点存储主键值

哈希索引

• 特点

  • 查找O（1）
  • 无有序性，无法排序、分组
  • 只支持精确查找

• 自适应哈希索引

  • 当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引

全文索引

• MyISAM存储引擎支持全文索引，可以查找文本中的关键字（InnoDB新版本也支持）
• 使用倒排索引记录着关键词到文档的映射

空间数据索引

优化

独立的列

• 索引列不能是表达式的一部分，也不能是函数的参数

多列索引

• 使用多列索引比使用多个单列索引性能更好

索引列的顺序

• 让选择性最强的索引列放在前面

前缀索引

• 对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符

覆盖索引

• 索引包含所有需要查询的字段的值