一、索引的本质MySQL官方对索引的定义为索引Index是帮助MySQL高效获取数据的数据结构。提取句子主干就可以得到索引的本质索引是数据结构。数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找linear search这种复杂度为O(n)的算法在数据量很大时显然是糟糕的好在计算机科学的发展提供了很多更优秀的查找算法例如二分查找binary search、二叉树查找binary tree search等。如果稍微分析一下会发现每种查找算法都只能应用于特定的数据结构之上例如二分查找要求被检索数据有序而二叉树查找只能应用于二叉查找树上但是数据本身的组织结构不可能完全满足各种数据结构例如理论上不可能同时将两列都按顺序进行组织所以在数据之外数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用指向数据这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。二、B-Tree平衡多路查找树B-Tree是为磁盘等外存储设备设计的一种平衡查找树。系统从磁盘读取数据到内存时是以磁盘块block为基本单位的位于同一个磁盘块中的数据会被一次性读取出来而不是需要什么取什么。InnoDB存储引擎中有**页Page**的概念页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB。可通过参数innodb_page_size将页的大小设置为4K、8K、16K。可通过如下命令查看页的大小mysqlshow variables like innodb_page_size;而系统一个磁盘块的存储空间往往没有这么大因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到内存时会以页为基本单位在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置这将会减少磁盘I/O次数提高查询效率。B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree首先定义一条记录为一个二元组[key, data] **key为记录的键值对应表中的主键值data为一行记录中除主键外的数据。**对于不同的记录key值互不相同。如下图所示为一个3阶的B-Tree每个节点占用一个盘块的磁盘空间一个节点上有两个升序排序的关键字和三个指向子树根节点的指针指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例关键字为17和35P1指针指向的子树的数据范围为小于17P2指针指向的子树的数据范围为17~35P3指针指向的子树的数据范围为大于35。模拟查找关键字29的过程1.根据根节点找到磁盘块1读入内存。【磁盘I/O操作第1次】2.比较关键字29在区间17,35找到磁盘块1的指针P2。3.根据P2指针找到磁盘块3读入内存。【磁盘I/O操作第2次】4.比较关键字29在区间26,30找到磁盘块3的指针P2。5.根据P2指针找到磁盘块8读入内存。【磁盘I/O操作第3次】6.在磁盘块8中的关键字列表中找到关键字29。分析上面过程发现需要3次磁盘I/O操作和3次内存查找操作。由于内存中的关键字是一个有序表结构可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数使每次磁盘I/O取到内存的数据都发挥了作用从而提高了查询效率。2.1 叶子节点非叶子节点整棵B树由多层磁盘页组成分为两类节点1. 非叶子节点目录层根节点、中间分支节点位置树的上层不在最底部不存真实业务数据存储内容索引 key 子页面指针相当于目录标题 页码作用路由查找缩小查询范围指引找到底层叶子特点一棵树只有少量非叶子节点体积小容易缓存到内存。2. 叶子节点数据层树最底层同一高度位置整棵树最底下一层没有子页面 存储真实数据 主键聚簇索引完整一行所有字段 普通二级索引只存主键 额外有双向链表指针所有叶子按索引从小到大串起来 所有查询最终必须走到叶子节点才能拿到数据 数量极多绝大多数存在磁盘很难全部缓存。三、BTreeBTree是在B-Tree基础上的一种优化使其更适合实现外存储索引结构InnoDB存储引擎就是用BTree实现其索引结构。从上图中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值还有data值。而每一个页的存储空间是有限的如果data数据较大时将会导致每个节点即一个页能存储的key的数量很小当存储的数据量很大时同样会导致B-Tree的深度较大增大查询时的磁盘I/O次数进而影响查询效率。在BTree中所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上而非叶子节点上只存储key值信息这样可以大大加大每个节点存储的key值数量降低BTree的高度。BTree相对于B-Tree有几点不同1.非叶子节点只存储键值信息。2.所有叶子节点之间都有一个链指针3.数据记录都存放在叶子节点中将上面的B-Tree优化由于BTree的非叶子节点只存储键值信息假设每个磁盘块能存储4个键值及指针信息则变成BTree后其结构如下图所示通常在BTree上有两个头指针一个指向根节点另一个指向关键字最小的叶子节点而且所有叶子节点即数据节点之间是一种链式环结构。因此可以对BTree进行两种查找运算一种是对于主键的范围查找和分页查找另一种是从根节点开始进行随机查找。四、为什么使用B-TreeBTree磁盘默认一页大小16KBInnoDB page_size一页就是 B 树一个节点。一般来说索引本身也很大不可能全部存储在内存中因此索引往往以索引文件的形式存储的磁盘上。这样的话索引查找过程中就要产生磁盘I/O消耗相对于内存存取I/O存取的消耗要高几个数量级所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。4.1主存存取原理目前计算机使用的主存基本都是随机读写存储器RAM现代RAM的结构和存取原理比较复杂这里抛却具体差别抽象出一个十分简单的存取模型来说明RAM的工作原理。从抽象角度看主存是一系列的存储单元组成的矩阵每个存储单元存储固定大小的数据。每个存储单元有唯一的地址现代主存的编址规则比较复杂这里将其简化成一个二维地址通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。4.2 主存的存取过程当系统需要读取主存时则将地址信号放到地址总线上传给主存主存读到地址信号后解析信号并定位到指定存储单元然后将此存储单元数据放到数据总线上供其它部件读取。写主存的过程类似系统将要写入单元地址和数据分别放在地址总线和数据总线上主存读取两个总线的内容做相应的写操作。这里可以看出主存存取的时间仅与存取次数呈线性关系因为不存在机械操作两次存取的数据的“距离”不会对时间有任何影响例如先取A0再取A1和先取A0再取D3的时间消耗是一样的。4.3 磁盘存取原理上面说过索引一般以文件形式存储在磁盘上索引检索需要磁盘I/O操作。与主存不同磁盘I/O存在机械运动耗费因此磁盘I/O的时间消耗是巨大的。下图是磁盘的整体结构示意图一个磁盘由大小相同且同轴的圆形盘片组成磁盘可以转动各个磁盘必须同步转动。在磁盘的一侧有磁头支架磁头支架固定了一组磁头每个磁头负责存取一个磁盘的内容。磁头不能转动但是可以沿磁盘半径方向运动实际是斜切向运动每个磁头同一时刻也必须是同轴的即从正上方向下看所有磁头任何时候都是重叠的不过目前已经有多磁头独立技术可不受此限制。盘片被划分成一系列同心环圆心是盘片中心每个同心环叫做一个磁道所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段每个段叫做一个扇区每个扇区是磁盘的最小存储单元。为了简单起见我们下面假设磁盘只有一个盘片和一个磁头。当需要从磁盘读取数据时系统会将数据逻辑地址传给磁盘磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址即确定要读的数据在哪个磁道哪个扇区。为了读取这个扇区的数据需要将磁头放到这个扇区上方为了实现这一点磁头需要移动对准相应磁道这个过程叫做寻道所耗费时间叫做寻道时间然后磁盘旋转将目标扇区旋转到磁头下这个过程耗费的时间叫做旋转时间。4.4 局部性原理与磁盘预读由于存储介质的特性磁盘本身存取就比主存慢很多再加上机械运动耗费磁盘的存取速度往往是主存的几百分分之一因此为了提高效率要尽量减少磁盘I/O。为了达到这个目的磁盘往往不是严格按需读取而是每次都会预读即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。局部性原理1.当一个数据被用到时其附近的数据也通常会马上被使用2.程序运行期间所需要的数据通常比较集中3.由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此对于具有局部性的程序来说预读可以提高I/O效率。预读的长度一般为页page的整倍数。页是计算机管理存储器的逻辑块硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块每个存储块称为一页在许多操作系统中页得大小通常为4k主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时会触发一个缺页异常此时系统会向磁盘发出读盘信号磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中然后异常返回程序继续运行。B-/Tree索引的性能分析上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析根据B-Tree的定义可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理将一个节点的大小设为等于一个页这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的在实际实现B-Tree还需要使用如下技巧1.每次新建节点时直接申请一个页的空间这样就保证一个节点物理上也存储在一个页里加之计算机存储分配都是按页对齐的就实现了一个node只需一次I/O。2.B-Tree中一次检索最多需要h-1次I/O根节点常驻内存渐进复杂度为O(h)O(logdN)O(h)O(logdN)。一般实际应用中出度d是非常大的数字通常超过100因此h非常小通常不超过3。综上所述用B-Tree作为索引结构效率是非常高的。而红黑树这种结构h明显要深的多。由于逻辑上很近的节点父子物理上可能很远无法利用局部性所以红黑树的I/O渐进复杂度也为O(h)效率明显比B-Tree差很多。BTree更适合外存索引原因和内节点出度d有关。从上面分析可以看到d越大索引的性能越好而出度的上限取决于节点内key和data的大小dmaxfloor(pagesize/(keysizedatasizepointsize))dmaxfloor(pagesize/(keysizedatasizepointsize))floor表示向下取整。由于BTree内节点去掉了data域因此可以拥有更大的出度拥有更好的性能。