MySQL索引篇

索引概念

概念：索引是提高mysql查询效率的数据结构。总的一句话概括就是索引是一种提高查询效率的数据结构。
数据库查询是数据库的最主要功能之一。设计者们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。
最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如：有顺序查找、折半查找、快速查找等。
但是，每种查找算法都只能应用于特定的数据结构之上，例如顺序查找依赖于顺序结构，折半查找通过二叉查找树或红黑树实现二分搜索。
因此，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这种数据结构，就是索引。

索引性能分析

目前，大多数数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。B+ 树索引是 B+ 树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。
从最早的平衡二叉树演化而来的。B+ 树是由二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree）逐步优化而来。
那么为什么mysql的索引选择B+数呢？
有序数组、Hash索引、红黑树、二叉查找树、AVL树也可以作为数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B树或者B+树，这里结合各个索引的特点以及计算的组成原理来深入的分析。
但是，对于Mysql来说适合它的才是最好的查询，一方面要实现高效的查询，除了简单的条件查询，还要支持有序的高效索引的范围查询、分组。
有序数组在等值查询和范围查询性能都是非常好的，那为什么又不用有序数组作为索引呢？因为对于数组而言作为索引更新的成本太高，新增数据要把后面的数据都往后移一位，所以也不采用有序数组作为索引的底层实现。
hash是以key-value的形式进行存储，适合于等值查询的场景，查询的时间复杂度为O(1)，因为hash储存并不是有序的，所以对于范围查询就可能要遍历所有数据进行查询，而且不同值的计算还会出现hash冲突，所以hash并不适合于做Mysql的索引。
另一方面就是除了查询的效率要高，还要有高效的读取数据效率（io），我们都知道计算机的随机磁盘io效率是非常低下的。
那么为什么硬盘的存取会如此的慢呢？
这个就要讲硬盘的读写原理，硬盘有很多种，但是都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部分组成。
所有的盘片都固定在一条轴上，那条轴叫做盘片主轴，所有的盘片都是绝对平行的，也形成一个柱体，每个盘片上都有一个磁头，每个磁头都在同一轴线上，就是从上方往下看，磁头是绝对重叠的。
所有的磁头连在一个磁头控制器上，由磁头控制器负责各个磁头的运动，磁头可沿盘片的半径方向移动，实际上是斜切运动，每个磁头同一时刻必须是同轴的盘片以每分钟数千转到上万转的速度在高速运转，这样磁头就能对盘片上的指定位置进行数据的读写操作：
磁盘数据的读写原理
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。
磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。
为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
即一次磁盘的读写操作完成过程由三个动作组成：

• 寻道（时间）：磁头移动定位到指定磁道。
• 旋转延迟（时间）：等待指定扇区从磁头下旋转经过。
• 数据传输（时间）：数据在磁盘与内存之间的实际传输

  额外知识：

  • 盘面：硬盘的每一个盘片都有上下两个盘面，一般每个盘面都会得到利用，都可以存储数据，盘面号又叫磁头号，因为每一个有效盘面都有一个对应的读写磁头。
  • 磁道：磁盘在格式化时被划分成许多同心圆，这些同心圆轨迹叫做磁道，磁道从外向内从 0 开始顺序编号，信息以脉冲串的形式记录在这些轨迹中，这些同心圆不是连续记录数据，而是被划分成一段段的圆弧。
  • 所有盘面上的同一磁道构成一个圆柱，通常称作柱面。所有盘面上的同一磁道构成一个圆柱，通常称作柱面。数据的读 / 写按柱面进行，而不按盘面进行，当一个磁道写满数据后，就在同一柱面的下一个盘面来写，一个柱面写满后，才移到下一个扇区开始写数据，读数据也按照这种方式进行，这样就提高了硬盘的读 / 写效率。

提高磁盘数据读写原理
局部性原理与磁盘预读。由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。
为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
所以，程序运行期间所需要的数据通常应当比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）4k的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。
当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

所以，硬盘中由于涉及到机械运动，所以一次的磁盘IO消耗的时间是非常大的，于内存的读取速度相比，就好比光速与声速的比较。

因此，假如内存条件允许的话，Mysql巴不得把所有的数据一次性加载到内存中进行读写。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。
服务器的内存的大小也是限制的，一个服务器中可能不止跑着Mysql一个进行，多多少少都有可能二三十个进行，每个进行都需要操作系统分配内存。
这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，硬盘I/O存取的消耗要高几个数量级，查找过程中磁盘I/O的存取次数。
Mysql中的一些大的数据表，一个表就有可能几个G，索引结构也很大，那服务器内存不得撑爆了。
所以，必须做一个取舍，在内存与磁盘中进行衡量，数据尽量放在内存中，而在少量的数据在磁盘中，读取磁盘的次数控制到最少，也就是对于Mysql的性能影响到最小，加上磁盘数据读写原理来提高数据的读取效率。
那么在众多树的条件下，B+树又是以怎么样的又是脱颖而出呢？下面我们来聊一聊B树、B-树、B+树、红黑树性能。

二叉树、红黑树、AVL树、B树、B+树性能分析

B树性能分析：B树是二叉查找平衡树，但是B树一个节点只存一个关键字，在大量数据的时候，B树树高非常大，性能低下：

甚至在极端的情况下，因为二叉搜索树不存在平衡算法，所以在某些特殊的情况下，二叉搜索树等同于线性，出现蹩脚的情况，设计者们发现降低树的高度自然就可以提高查找效率：

红黑树和AVL树是在二叉树的基础上机上加上平衡算法，红黑树确保没有一条路径会比其它路径长出两倍，它是弱平衡树而AVL是严格的平衡，所以相对于二叉树的蹩脚情况做了很大的改进，加入了平衡算法：

但是，同样还是存在数据量大导致树非常高的问题，所以现在的目标就是压缩树的高度。
B树基于减少树的高度上，B树是一种多路搜索树，每个节点都可以有多于两个子节点，并不是二叉的：

B树与B+树最大的区别就是B的非叶子节点可以存储数据，而B+树只有叶子结点才可以存储数据，B树是多路搜索树，一个节点可以存储很多数据，所以B树的高度大大减小。
但是B树相对于B+树来说，在查找数据的时候，由于每一个节点都有可能包含目标数据，所以查找总是从根节点进行向下搜索，这个特点会带来大量的随机io。
而在B+树种，因为叶子结点才会存储数据（InnoDB），这样子相比B树一个页大小存储的索引数据就更多了（16K），并且叶子结点通过双向指针指向相邻的节点，依次连接。
并且相邻结点是有序的，所以对于范围查找是非常方便的，获取到第一个符合条件的，然后通过指针，往后获取数据，直到最后一个不满足条件为止。
所以总结来说：B+树是多叉树，一个数据页的大小是16kb，在1-3的树高就能存储10亿级以上的数据，也就是只要访问磁盘1-3次就足够了，并且B+树的叶子结点上一个叶子结点有指针指向下一个叶子结点，便于范围查询：

B+树索引原理

上面也大概说了一下B+树的介绍，在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。
在B+树的结构中，只在叶子节点存储数据，在非叶子节点中只存储的索引，在非叶子节点中可以有更大的空间储存更多的索引，这样B+树的出度d就可以大大的增加，从而降低的B+树的高度h，B树中一个节点的大小为一个page的大小，也就是一次IO的读取，h越小IO的次数就可以减少：
dmax=floor(pagesize/(keysize+datasize+pointsize))
floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
我们来看看B+树的搜索过程，Mysql的InnoDB的索引的结构如下图所示，假设我们要搜索id为15的数据：

1. 根据根节点找到磁盘块 1，读入内存，一般根节点也会常驻内存，甚至可以省略一次磁盘IO操作。【磁盘 I/O 操作第 1 次】
2. 比较id 15在区间28的左边，于是根据p1找到磁盘2。
3. 将磁盘2读入内存，查找结果15在（10,17）之间。【磁盘 I/O 操作第 2 次】
4. 然后根据磁盘2的指针p2找到磁盘块5，读入内存。【磁盘 I/O 操作第 3 次】
5. 最后根据id=15找到对应的数据，返回结果。

所以根据上面的查找只需要至多三次的磁盘IO就可以找到对应的数据。从上面的B+树的原理图中非叶子节点构成了类似于一个一个目录一样，也可以叫做索引页，最后找到叶子结点的数据。