MySQL高级篇之索引结构

索引结构

• MySQL 的索引是在存储引擎层实现的，不同的存储引擎有不同的索引结构，主要包含以下几种 ：

  索引结构	描述
  B+Tree索引	最常见的索引类型，大部分引擎都支持 B+ 树索引
  Hash索引	底层数据结构是用哈希表实现的, 只有精确匹配索引列的查询才有效, 不支持范围查询
  R-tree(空间索引）	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
  Full-text(全文索引)	是一种通过建立倒排索引，快速匹配文档的方式

  索引结构	InnoDB	MyISAM	Memory
  B+Tree索引	支持	支持	支持
  Hash 索引	不支持	不支持	支持
  R-Tree 索引	不支持	支持	不支持
  Full-text	5.6版本之后支持	支持	不支持

  总结：

  • 如果没有特别指明，都是使用 B+Tree 结构组织的索引。
  • 只有 Memory 存储引擎支持 Hash 索引。
  • 只有 MyISAM 存储引擎支持 R-Tree 索引。

1. Hash

• Hash表，在 Java 中的 HashMap，TreeMap 就是 Hash 表结构，以键值对的方式存储数据。我们使用 Hash 表存储，表数据 Key 可以存储索引列，Value 可以存储行记录或者行磁盘地址。Hash 表在等值查询时效率很高，但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。
• InnoDB: 具有自适应 hash 功能，hash索引是存储引擎根据 B+Tree 索引在指定条件下自动构建的

2. B-Tree

• 背景：

  • 二叉树在大部分情况下都可以提高检索速度，但在顺序插入时，会形成一个链表，查询性能大幅度降低。数据量大的情况下，层级较深，检索速度慢。

  • 红黑树可以很好的解决顺序插入的问题，不过在数据量大的情况下，也存在层级较深，检索速度慢的问题。

• 因为在 MySQL 的 InnoDB 存储引擎一次 IO 会读取的一页（默认一页16K）的数据量，而二叉树一次 IO 有效数据量只有16字节，空间利用率极低。为了最大化利用一次 IO 空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘 IO 就可以查询到数据。磁盘 IO 次数变少了，查询数据的效率也就提高了。

• 这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：

  1. B树的节点中存储着多个元素，每个内节点有多个分叉。
  2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
  3. 父节点当中的元素不会出现在子节点中。
  4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

  

• 缺点：

  1. B树不支持范围查询的快速查找。如果想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
  2. 如果 data 存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

3. B+Tree

• B+Tree，在 B+Tree 基础上进行了改造。B+Tree 和 B-Tree 最主要的区别在于非叶子节点是否存储数据的问题，即：

  • B-Tree：非叶子节点和叶子节点都会存储数据。
  • B+Tree：只有叶子节点才会存储数据，非叶子节点只存储键值。叶子节点形成一个单向链表，非叶子节点仅仅起到索引数据的作用，具体的数据都是在叶子节点存放的 。

• MySQL 索引数据结构对经典的 B+Tree 进行了优化。在原 B+Tree 的基础上，增加一个指向相邻叶子节点的链表指针，即叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。进一步提高区间访问的性能，利于排序。

  

• MySQL 对 B+Tree 进行了优化之后，可以保证等值和范围查询的快速查找。

面试题

• 为什么 InnoDB 存储引擎选择使用 B+Tree 索引结构？（B+Tree 的优点？）

1. 相对于二叉树，层级更少，搜索效率高。
2. 对于 B-Tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针也跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低。
3. 相对于 Hash 索引，B+Tree 支持范围匹配及排序操作。