MySQL创建高性能索引的全步骤

一、索引基础

1. 索引的类型

1.1 B-Tree 索引

大多数mysql存储引擎默认使用的是B+树的索引，不同的存储引擎用不同的方式使用B+树索引，MyISAM使用前缀压缩技术使得索引更小，但是InnoDB则按照元数据格式进行存储；MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。

B树 和 B+ 树

B树：

B+树：

区别：

• B树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中
• 在 B树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而 B+树中每个记录 的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看 B树的性能好像要比 B+树好，而在实际应用中却是 B+树的性能要好些。因为 B+树的非叶子节点不存放实际的数据， 这样每个节点可容纳的元素个数比 B树多，树高比 B树小，这样带来的好处是减少磁盘访问次数。尽管 B+树找到 一个记录所需的比较次数要比 B树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中 B+树的性能可能还会好些，而且 B+树的叶子节点使用指针连接在一起，方便顺序遍历（例如查看一个目录下的所有 文件，一个表中的所有记录等），这也是很多数据库和文件系统使用 B+树的缘故
  

为什么说 B+树比 B-树更适合实际应用中操作系统的文件索引和数据库索引？

• B+树的磁盘读写代价更低
  • B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点 的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了
• B+树的查询效率更加稳定
  • 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相编程客栈同，导致每一个数据的查询效率相当
    

为什么不用红黑树？

• B+树更少的查找次数
  • 平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。
  • 红黑树的出度为 2，而 B+树 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+树 大非常多，查找的次数也就更多。
• B+树利用磁盘预读特性
  • 为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。
  • 操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入
    

1.2 哈希索引

哈希索引基于哈希表实现，对于每一行数据，存储引擎会对所有的索引列计算一个哈希码，通过哈希码能以 O(1) 时间进行查找，但是无法用于排序与分组，并且只支持精确查找，无法用于部分查找和范围查找。

在MySQL 中，只有Memory引擎显式支持哈希索引

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

1.3 空间数据索引（R-Tree）

MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。

MySQL创建高性能索引的全步骤