稀疏、密集索引与搜索引擎

稀疏索引与密集索引的区别

• 密集索引文件中每一个搜索码值都对应一个索引值
  • 叶子结点不仅仅保存键值，还保存有其他列的信息。
  • 密集索引决定了物理表的排列顺序，所以一个表只创建一个密集索引，通常是主键。
• 稀疏索引文件只为索引码的某些值建立索引项
  • 叶子结点仅保存了键位信息和该行数据的地址（有的稀疏索引仅保存了键位信息及其主键）。
  • 定位到叶子结点之后仍然需要通过地址或者主键信息进一步定位到数据。

在MySQL中的具体分析

主要存储引擎

• MysISAM

  • 其索引无论是主键索引还是唯一键索引或者普通索引，均为稀疏索引

• InnoDB

  • 必须有且仅有一个密集索引

    • 如果一个主键被定义，则主键作为密集索引
    • 如果没有主键被定义，则第一个唯一非空索引作为密集索引
    • 若上述均不满足，InnoDB内部会生成一个隐藏主键作为密集索引

  • 非主键索引（稀疏索引）的叶子结点并不存储行数据的物理地址，而是存储该行的主键值。

    故稀疏索引包含两次查找，一次查找到主键值，第二次根据主键值找到数据

MyISAM和InnoDB索引存储对比图

• InnoDB使用密集索引，将主键组织到B+树中，行数据就存储在叶子结点上
  • 即在查找主键时就会把行数据一同加载
  • 若对稀疏索引进行筛选就会通过两次查找
• MyISAM的索引均为稀疏索引，结点结构完全一致，表数据存储在独立的地方，行数据与索引分开存储。