深入了解MySQL的索引

（一）关于存储引擎       

       创建合适的索引是SQL性能调优中最重要的技术之一。在学习创建索引之前，要先了解MySql的架构细节，包括在硬盘上面如何组织的，索引和内存用法和操作方式，以及存储引擎的差异如何影响到索引的选择。

       MySQL有很多种衍生版本，这些衍生版本支持更多不同种类的存储引擎。本文主要讨论三种MySQL引擎。

       MyISAM 一种非事务性的存储引擎，是MySQL 5.5之前版本默认的存储引擎。

       InnoDB  最流行的事务性存储引擎，从5.5版开始成为MySQL默认的引擎。

       Memory 基于内存的，非事务性的以及非持久性的存储引擎。

       注意：

        从5.5版本开始，MySQL表的默认存储引擎从MyISAM换成InnoDB，将会使用户安装那些依赖默认设置或者专门为MyISAM编写的软件包时带来很大的影响。

（二）MySQL索引类型

        MySQL支持在所有关系数据库表中创建主键、唯一键、不唯一的非主码索引等多种类型的索引。此外MySQL还支持纯文本和空间索引类型。

       MySQL内置的存储引擎对各种索引技术有不同的实现方式，包括：B-树，B+树，R-树以及散列类型。

       索引数据结构理论：

       1.B-树

       B-树中有两种节点类型：索引节点和叶子节点。叶子节点是用来存储数据的，而索引节点则用来告诉用户存储在叶子节点中的数据顺序，并帮助用户找到相应的数据。

       B-树的搜索，从根节点开始，对节点内的关键字有序进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子节点，重复。直到所对应的儿子指针为空，或已经是叶子节点。

       B-树是一种多路搜索树：

       (1). 定义任意非叶子节点最多有M个儿子，且M>2;

       (2). 根节点的儿子数为[2,M];

       (3). 除根节点以外的非叶子节点的儿子数为[M/2,M];

       (4). 每个节点存放至少M/2-1(取上整)和至多M-1个关键字;

       (5). 非叶子节点的关键字个数=指向儿子节点的指针的个数-1;  

       (6). 非叶子节点的关键字：k[i]<k[i+1];

       (7). 非叶子节点的指针：p[1]，p[2]，·····，p[M]；其中p[1]指向的关键字小于k[1]的子树，p[M]指向的关键字大于K[m-1]的子树;

       (8). 所有的叶子节点位于同一层; 

      2.B+树

       B+树数据结构是B-树实现的增强版本。尽管B+树支持B-树索引的所有特性，它们之间最显著的不同点在于B+树中底层数据是根据被提及的索引列进行排序的。B+树还通过叶子节点之间的附加引用来优化扫描性能。

       B+搜索和B-搜索不同，区别是B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），其性能等价于关键字全集做一次二分搜索。

      B+树的特性：

     （1）所有关键字都出现在叶子节点的链表中，叶子节点相当于存储数据的数据层。

     （2）不可能在非叶子节点上命中。

     （3）非叶子节点相当于是叶子节点的索引，叶子节点相当于数据层。

     3.散列

     散列表数据结构是一种很简单的概念，它将一种算法应用到给定值中以在底层数据存储系统中返回一个唯一的指针或位置。散列表的优点是始终以线性时间复杂度找到需要读取的行的位置，而不像B-树那样需要横跨多层节点来确定位置。

     4.通信R-树

    R-树数据结构支持基于数据类型对几何数据进行管理。目前只有MyISAM使用R-树实现支持空间索引，使用空间索引也有很多限制，比如只支持唯一的NOT NULL列等。

    5.全文本

     全文本结构也是一种MySQL采用的基本数据结构。这种数据结构目前只有当前版本MySQL中的MyISAM存储引擎支持。5.6版本将要在InnoDB存储引擎中加入全文本功能。全文本索引在大型系统中并没有什么实用的价值，因为大规模系统有很多专门的文件检索产品。所以不用在介绍。

MySQL实现

       对B-树，B+树和散列等数据结构的基本概念有了一些了解之后，我们就可以开始讨论MySQL通过支持它们的存储引擎如何实现不同的算法。同时每种实现也对磁盘和内存使用情况有不同的影响，这一点在大型数据库系统中是非常重要的考虑因素。

1.MyISAM的B-树

     MyISAM存储引擎使用B-树数据结构来实现主码索引、唯一索引以及非主码索引。在MyISAM实现数据目录和数据库模式子目录中，用户可以找到和每个MySQL表对应的.MYD和.MYI文件。数据库表上定义的索引信息就存储在MYI文件中，该文件的块大小是1024字节。这个大小是可以通过myisam-block-size系统变量分配。

    $  ls -1h /var/lib/mysql/book/source_words.MY*

    -rw-rw---- 1 mysql mysql  9.2M 2015-05-07 19:08

    source_words.MYD

   -rw-rw---- 1 mysql mysql  7.8M 2015-05-07 19:08

    source_words.MYI

     这些文件结构的内部格式可以从MySQL免费源代码中找到，也可以查看MySQL内部手册。

     在MyISAM中，非主码索引的B-树结构存储索引值和一个指向主码数据的指针，这是MyISAM和InnoDB的一个显著区别。这一点导致了两个存储引擎的索引的不同工作方式。

     MyISAM索引是在内存的一个公共缓存中管理的，这个缓存的大小可以通过key_buffer_size或者其他命名键缓存来定义。这是根据统计和规划的表索引的大小来设定缓存大小时主要的考虑因素。

2. InnoDB的B+树聚簇主码

      InnoDB存储引擎在它的主码索引（也被称为聚簇主码）中使用了B+树，这种结构把所有数据都和对应的主码组织在一起，并且在叶子节点这一层上添加额外的向前和向后的指针，这样就可以更方便地进行范围扫描。

      在文件系统层面，所有InnoDB数据和索引信息都默认在公共InnoDB表空间中管理，否则管理员就通过innodb_data_file_path这个变量指定文件路径。这是一个叫ibdatal文件。

      由于InnoDB用聚簇主码存储数据，底层信息占用的磁盘空间的大小很大程度上取决于页面的填充因子。对于按序排列的主码，InnoDB会用16K页面的15/16作为填充因子。对于不是按序排列的主码，默认情况下InnoDB会插入初始数据的时候为每一个页面分配50%作为填充因子。

      在改索引的实现方式中B+树的叶子节点上是data就是数据本身，key为主键，如果是一般索引的话，data便会指向对应的主索引。在B+树的每一个叶子节点上面增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+树。其目的是提高区间访问的性能。

3.InnoDB的B-树非主码

     InnoDB中的非主码索引使用了B-树数据结构，但InnoDB中的B-树结构实现和MyISAM中并不一样。在InnoDB中，非主码索引存储的是主码的实际值。而MyISAM中，非主码索引存储的包含主码值的数据指针。这一点很重要。首先，当定义很大的主码的时候，InnoDB的非主码索引可能回更大，随着非主码索引数量的增加，索引之间大小差别可能会变得很大。另一个不同点在于非主码索引当前可以包含主键的值，并且可以不是索引必须有的部分。

4.内存散列索引

    在默认MySQL的引擎索引中，只有MEMORY引擎支持散列数据结构，散列结构的强度可以表示为直接键查找的简单性，散列索引的相似度模式匹配查询比直接查询慢。也可以为MEMORY引擎指定一个B-树索引实现。

5.内存B-树索引

   对于大型MEMORY表来说，使用散列索引进行索引范围搜索的效率很低，B-树索引在执行直接键查询时确实比使用默认的散列索引快。根据B-树的不同深度，B-树索引在个别操作中的确可能比散列算法快。

6.InnoDB内部散列索引

    InnoDB存储引擎在聚簇B+树索引中存储主码：但在InnoDB内部还是使用内存中的散列表来更高效地进行主码查询。这个机制有InnoDB存储引擎来管理，用户只能通过innodb_adaptive_hash_index配置项来选择是否启用这个唯一的配置选项。