MYSQL索引背后的数据结构和算法原理

MYSQL索引背后的数据结构和算法原理

本文内容来自于：http://blog.codinglabs.org/articles/theory-of-mysql-index.html

​ http://blog.csdn.net/zheng0518/article/details/76302167

一、数据结构及算法基础

• 1.1索引的本质

  MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

  • 从查询算法的角度进行优化->顺序查找复杂度太大->二分查找需要数据排序->二叉树查找需要数据本身以二叉搜索树的形式组织。
  • 所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
  • 实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，为什么？？？

• B-Tree和B+Tree

  • B-Tree性能分析。
  • B+Tree性能分析。

• 为什么使用B-Tree、B+Tree

二、MYSQL索引实现

在mysql中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

• 2.1 MyISAM存储引擎

  • MyISAM存储引擎使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址。

    MyISAM引擎主键索引.gif

  • 在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

    MyISAM引擎辅助索引.gif

  • MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

  • MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

  虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

  ​

• 2.2 InnoDB存储引擎

  • 第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。如图：

    InnoDB引擎主键索引.gif

    可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

  • 第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。 换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

    InnoDB引擎辅助索引.gif

    这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

三、索引使用策略及优化

MYSQL优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。