第06章 索引的数据结构【2.索引及调优篇】【MySQL高级】3

类比

有个文件夹下的文件可以按很多字段排序

例如名称、修改日期、类型、大小

如果对每个字段都进行通过聚簇索引来排序，那耗得内存也太大了。所有只需要用一个关键字来作为聚簇索引进OK了，用来排序其他字段的数据项节点执行存储其字段及关键字，也就是二级索引，再通过回表，就可操作了。

3. 联合索引

其属于非聚簇索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说想让B+树按

照 c2和c3列 的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照c2列进行排序
• 在记录的c2列相同的情况下，采用c3列进行排序

为c2和c3列建立的索引的示意图如下：

如图所示，需要注意以下几点:

每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。

B+树叶子节点处的用户记录由c2、c3和主键c1列组成

注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引 ，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：

建立联合索引只会建立如上图一样的1棵B+树。

为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

3.4 InnoDB的B+树索引的注意事项

1. 根页面位置万年不动

前边介绍B+树索引的时候，为了理解上的方便，先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，实际上B+树的形成过程是这样的:

自上而下

每当为某个表创建一个B+树索引(聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录

随后向表中插入用户记录时，先把用户记录存储到这个根节点中

当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值)的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页

这个过程需要注意的是:一个B+树索引的根节点自诞生起，便不会再移动。这样只要对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

2. 内节点(非叶节点)中目录项记录的唯一性

B+树索引的内节点中目录项记录的内容是索引列＋页号的搭配，但是这个搭配对于二级索引来说有点不严谨。还拿index_demo表为例，假设这个表中的数据是这样的:

如果二级索引中目录项记录的内容只是索引列＋页号的搭配的话，那么为c2列建立索引后的B+树应该长这样:


如果想新插入一行记录，其中c1、c2、c3的值分别是: 9、1、 ‘c’，那么在修改这个为c2列建立的二级索引对应的B+树时便碰到了个大问题:由于页3中存储的目录项记录是由c2列＋页号的值构成的，页3中的两条目录项记录对应的c2列的值都是1，而新插入的这条记录的c2列的值也是1，那这条新插入的记录到底应该放到页4中，还是应该放到页5中啊?答案是:对不起，懵了。

为了让新插入记录能找到自己在那个页里，需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的:

• 索引列的值
• 主键值
• 页号
  也就是把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，所以为c2列建立二级索引后的示意图实际上应该是这样子的:
  
  这样再插入记录(9，1， ‘c’)时，由于页3中存储的目录项记录是由c2列＋主键＋页号的值构成的，可以先把新记录的c2列的值和页3中各目录项记录的c2列的值作比较，如果c2列的值相同的话，可以接着比较主键值，因为B+树同一层中不同目录项记录的c2列＋主键的值肯定是不一样的，所以最后肯定能定位唯一的一条目录项记录，在本例中最后确定新记录应该被插入到页5中。

3.一个页面最少存储2条记录

一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错!这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢?那就是目录层级非常非常非常多，而且最后的那个存放真实数据的目录中只能存放一条记录。费了半天劲只能存放一条真实的用户记录?所以InnoDB的一个数据页至少可以存放两条记录。

4. MyISAM中的索引方案

4.1 简介

B+树索引适用存储引擎如表所示：

即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是B+tree索引；而Memory默认的索引是Hash索引。

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

4.2 MylSAM索引的原理

我们知道InnoDB中索引即数据，也就是聚簇索引的那棵B+树的叶子节点中已经把所有完整的用户记录都包含了，而MyISAM的索引方案虽然也使用树形结构，但是却将索引和数据分开存储:

将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并没有刻意按照主键大小排序，所以并不能在这些数据上使用二分法进行查找

使用MyISAN存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAN会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值＋数据记录地址的组合。

下图是MyISAM索引的原理图：

这里设表一共有三列，假设以col1为主键，上图是一个MyISAM表的主索引(Primary key)示意。可以看出MylISAM的索引文件仅仅保存数据记录的地址。yISAM中，主键索引和二级索引(Secondary key)在结构上没有任何区别，只是主键索引要求key是唯一的，而二级索引的key可以重复（需要注意的是，MylSAM中没有聚簇索引和非聚簇索引之说）。如果在Col2上建立一个二级索引，则此索引的结构如下图所示:

4.3 MyISAM 与 InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：

① 在InnoDB存储引擎中，只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次回表操作（原因是没有聚簇索引），意味着MyISAM中建立的索引相当于全部都是二级索引

② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的 ，索引文件仅保存数据记录的地址

③ InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。

④ MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。

⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

小结:

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助。比如:

举例1:知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有二级索引都引用主键索引，过长的主键索引会令二级索引变得过大

举例2:用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择

5. 索引的代价

索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：

• 空间上的代价
  每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。
  时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且B+树每层节点都是按照索引列的值 从小到大的顺序排序 而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些 记录移位 ， 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。为了能建立又好又少的索引，需要学学这些索引在哪些条件下起作用

6. MySQL数据结构选择的合理性

从MysQL的角度讲，不得不考虑一个现实问题就是磁盘IO。如果能让索引的数据结构尽量减少硬盘的I/O操作，所消耗的时间也就越小。可以说，磁盘的I/0操作次数对索引的使用效率至关重要。

查找都是索引操作，一般来说索引非常大，尤其是关系型数据库，当数据量比较大的时候，索引的大小有可能几个G甚至更多，为了减少索引在内存的占用，数据库索引是存储在外部磁盘上的。当利用索引查询的时候，不可能把整个索引全部加载到内存，只能逐一加载，那么My$QL衡量查询效率的标准就是I/O磁盘次数。

6.1 全表遍历

这里都懒得说了。

6.2 Hash结构

Hash本身是一个函数，又被称为散列函数，它可以大幅提升检索数据的效率。

Hash算法是通过某种确定性的算法（比如MD5、SHA1、SHA2、SHA3）将输入转变为输出。相同的输入永远可以得到相同的输出，假设输入内容有微小偏差，在输出中通常会有不同的结果。

举例:如果想要验证两个文件是否相同，那么不需要把两份文件直接拿来比对，只需要让对方把Hash函数计算得到的结果告诉你即可，然后在本地同样对文件进行Hash函数的运算，最后通过比较这两个Hash 函数的结果是否相同，就可以知道这两个文件是否相同。

加速查找速度的数据结构。常见的有两类:

⑴树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(log2N);

⑵哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1);

采用Hash进行检索效率非常高，基本上一次检索就可以找到数据，而B+树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次IO操作，从效率来说Hash比 B+树更快。

在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[o…m-1]的槽位上

上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：


实验：体会数组全表遍历和hash表的查找方面的效率区别

  // 算法复杂度为 O(n)
  @Test
  public void test1() {
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
        long start = System.currentTimeMillis();
        for (int j = 1; j <= 100000; j++) {
            int temp = j;
            for (int i = 0; i < arr.length; i++) {
                if (temp == arr[i]) {
                    break;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("time： " + (end - start)); //time： 823
    }

  //算法复杂度为 O(1)
  @Test
  public void test2() {
        HashSet<Integer> set = new HashSet<>(100000);
        for (int i = 0; i < 100000; i++) {
            set.add(i + 1);
        }
        long start = System.currentTimeMillis();
        for (int j = 1; j <= 100000; j++) {
            int temp = j;
            boolean contains = set.contains(temp);
        }
        long end = System.currentTimeMillis();
        System.out.println("time： " + (end - start)); //time： 5
    }

Hash结构效率高，那为什么索引结构要设计成树型呢？

原因1: Hash索引仅能满足(=)(）和IN查询。如果进行范围查询，哈希型的索引，时间复杂度会退化为O(n);而树型的“有序"特性，依然能够保持O(log2N)的高效率。

原因2: Hash索引还有一个缺陷，数据的存储是没有顺序的，在ORDER BY的情况下，使用Hash索引还需要对数据重新排序。

原因3∶对于联合索引的情况，Hash值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询。

原因4:对于等值查询来说，通常Hash索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以,Hash索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。

Hash索引适用存储引擎如表所示:

Hash索引的适用性:

Hash索引存在着很多限制，相比之下在数据库中B+树索引的使用面会更广，不过也有一些场景采用Hash索引效率更高，比如在键值型（Key-Value）数据库中，Redis 存储的核心就是Hash表

MysQL中的 Memory存储引擎支持Hash存储，如果需要用到查询的临时表时，就可以选择Memory存储引擎，把某个字段设置为Hash索引，比如字符串类型的字段，进行Hash 计算之后长度可以缩短到几个字节。当字段的重复度低，而且经常需要进行等值查询的时候，采用Hash索引是个不错的选择。

另外，InnoDB本身不支持 Hash索引，但是提供自适应Hash 索引(Adaptive Hash Index)。什么情况下才会使用自适应Hash 索引呢?

如果某个数据经常被访问，当满足一定条件的时候（比如某个内容的查询数目超过某个值），就会将这个数据页的地址存放到Hash表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。这样让B+树也具备了Hash索引的优点。

采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。

可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

show variables like '%adaptive_hash_index';
/*
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON    |
+----------------------------+-------+
*/