MySQL索引原理及BTree（B-+Tree）结构详解
⽬录
摘要
本⽂以MySQL数据库为研究对象，讨论与数据库索引相关的⼀些话题。特别需要说明的是，MySQL⽀持诸多存储引擎，⽽各种存储引擎对索引的⽀持也各不相同，因此MySQL数据库⽀持多种索引类型，如BTree索引，哈希索引，全⽂索引等等。为了避免混乱，本⽂将只关注于BTree索引，因为这是平常使⽤MySQL时主要打交道的索引，⾄于哈希索引和全⽂索引本⽂暂不讨论。
⽂章主要内容分为三个部分。
第⼀部分主要从数据结构及算法理论层⾯讨论MySQL数据库索引的数理基础。
第⼆部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、⾮聚集索引及覆盖索引等话题。
第三部分根据上⾯的理论基础，讨论MySQL中⾼性能使⽤索引的策略。
数据结构及算法基础
索引的本质
MySQL官⽅对索引的定义为：索引（Index）是帮助MySQL⾼效获取数据的数据结构。提取句⼦主⼲，就可以得到索引的本质：索引是数据结构。
我们知道，数据库查询是数据库的最主要功能之⼀。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的⾓度进⾏优化。最基本的查询算法当然是（linear search），这种复杂度为O(n)的算法在数据量很⼤时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查算法，例如（binary search）、（binary tree search）等。如果稍微分析⼀下会发现，每种查算法都只能应⽤于特定的数据结构之上，例如⼆分查要求被检索数据有序，⽽⼆叉树查只能应⽤于上，但是数据本⾝的组织结构不可能完全满⾜各种数据结构（例如，理论上不可能同时将两列都按顺序进⾏组织），所以，在数据之外，数据库系统还维护着满⾜特定查算法的数据结构，这些数据结构以某种⽅式引⽤（指向）数据，这样就可以在这些数据结构上实现⾼级查算法。这种数据结构，就是索引。
看⼀个例⼦：
图1
图1展⽰了⼀种可能的索引⽅式。左边是数据表，⼀共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是⼀定物理相邻的）。为了加快Col2的查，可以维护⼀个右边所⽰的⼆叉查树，每个节点分别包含索引键值和⼀个指向对应数据记录物理地址的指针，这样就可以运⽤⼆叉查在O(log2n)O(log2n)的复杂度内获取到相应数据。
虽然这是⼀个货真价实的索引，但是实际的数据库系统⼏乎没有使⽤⼆叉查树或其进化品种（red-black tree）实现的，原因会在下⽂介绍。
B-Tree和B+Tree
⽬前⼤部分数据库系统及⽂件系统都采⽤B-Tree或其变种B+Tree作为索引结构，在本⽂的下⼀节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此⼴泛⽤于索引，这⼀节先单纯从数据结构⾓度描述它们。
B-Tree
为了描述B-Tree，⾸先定义⼀条数据记录为⼀个⼆元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满⾜下列条件的数据结构：
d为⼤于1的⼀个正整数，称为B-Tree的度。
h为⼀个正整数，称为B-Tree的⾼度。
每个⾮叶⼦节点由n-1个key和n个指针组成，其中d<=n<=2d。
每个叶⼦节点最少包含⼀个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
所有叶节点具有相同的深度，等于树⾼h。
key和指针互相间隔，节点两端是指针。
⼀个节点中的key从左到右⾮递减排列。
所有节点组成树结构。
每个指针要么为null，要么指向另外⼀个节点。
如果某个指针在节点node最左边且不为null，则其指向节点的所有key⼩于v(key1)v(key1)，其中v(key1)v(key1)为node的第⼀个key的值。
如果某个指针在节点node最右边且不为null，则其指向节点的所有key⼤于v(keym)v(keym)，其中v(keym)v(keym)为node的最后⼀个key的值。
如果某个指针在节点node的左右相邻key分别是keyikeyi和keyi+1keyi+1且不为null，则其指向节点的所有key⼩于
v(keyi+1)v(keyi+1)且⼤于v(keyi)v(keyi)。
图2是⼀个d=2的B-Tree⽰意图。
图2
由于B-Tree的特性，在B-Tree中按key检索数据的算法⾮常直观：⾸先从根节点进⾏⼆分查，如果到则返回对应节点的data，否则对相应区间的指针指向的节点递归进⾏查，直到到节点或到null指针，前者查成功，后者查失败。B-Tree上查算法的伪代码如下：
1. BTree_Search(node, key) {
2. if(node == null) return null;
3. foreach(node.key)
4. {
5. if(node.key[i] == key) return node.data[i];
6. if(node.key[i] > key) return BTree_Search(point[i]->node);
7. }
8. return BTree_Search(point[i+1]->node);
9. }
0. data = BTree_Search(root, my_key);
关于B-Tree有⼀系列有趣的性质，例如⼀个度为d的B-Tree，设其索引N个key，则其树⾼h的上限为logd((N+1)/2)logd((N+1)/2)，检索⼀个key，其查节点个数的渐进复杂度为O(logdN)O(logdN)。从这点可以看出，B-Tree是⼀个⾮常有效率的索引数据结构。
另外，由于插⼊删除新的数据记录会破坏B-Tree的性质，因此在插⼊删除时，需要对树进⾏⼀个分裂、合并、转移等操作以保持B-Tree性质，本⽂不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插⼊删除算法，有兴趣的朋友可以在本⽂末的参考⽂献⼀栏到相应的资料进⾏阅读。
B+Tree
B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使⽤B+Tree实现其索引结构。
与B-Tree相⽐，B+Tree有以下不同点：
每个节点的指针上限为2d⽽不是2d+1。
内节点不存储data，只存储key；叶⼦节点不存储指针。
图3是⼀个简单的B+Tree⽰意。
图3
由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点⼀般⼤⼩不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不⼀致，但是每个节点的域和上限是⼀致的，所以在实现中B-Tree往往对每个节点申请同等⼤⼩的空间。
⼀般来说，B+Tree⽐B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下⾯讨论。
带有顺序访问指针的B+Tree
⼀般在数据库系统或⽂件系统中使⽤的B+Tree结构都在经典B+Tree的基础上进⾏了优化，增加了顺序访问指针。
图4
如图4所⽰，在B+Tree的每个叶⼦节点增加⼀个指向相邻叶⼦节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的⽬的是为了提⾼区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当到18后，只需顺着节点和指针顺序遍历就可以⼀次性访问到所有数据节点，极⼤提到了区间查询效率。
这⼀节对B-Tree和B+Tree进⾏了⼀个简单的介绍，下⼀节结合存储器存取原理介绍为什么⽬前B+Tree是数据库系统实现索引的⾸选数据结构。
为什么使⽤B-Tree（B+Tree）
上⽂说过，红⿊树等数据结构也可以⽤来实现索引，但是⽂件系统及数据库系统普遍采⽤B-/+Tree作为索引结构，这⼀节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。
⼀般来说，索引本⾝也很⼤，不可能全部存储在内存中，因此索引往往以索引⽂件的形式存储的磁盘上。这样的话，索引查过程中就要产⽣磁盘I/O消耗，相对于内存存取，I/O存取的消耗要⾼⼏个数量级，所以评价⼀个数据结构作为索引的优劣最重要的指标就是在查过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查过程中磁盘I/O的存取次数。下⾯先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。
主存存取原理
⽬前计算机使⽤的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理⽐较复杂，这⾥本⽂抛却具体差别，抽象出⼀个⼗分简单的存取模型来说明RAM的⼯作原理。
图5
从抽象⾓度看，主存是⼀系列的存储单元组成的矩阵，每个存储单元存储固定⼤⼩的数据。每个存储单元有唯⼀的地址，现代主存的编址规则⽐较复杂，这⾥将其简化成⼀个⼆维地址：通过⼀个⾏地址和⼀个列地址可以唯⼀定位到⼀个存储单元。图5展⽰了⼀个4 x 4的主存模型。
主存的存取过程如下：
当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。
写主存的过程类似，系统将要写⼊单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。
这⾥可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是⼀样的。
磁盘存取原理
上⽂说过，索引⼀般以⽂件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨⼤的。
图6是磁盘的整体结构⽰意图。
图6
⼀个磁盘由⼤⼩相同且同轴的圆形盘⽚组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的⼀侧有磁头⽀架，磁头⽀架固定了⼀组磁头，每个磁头负责存取⼀个磁盘的内容。磁头不能转动，但是可以沿磁盘半径⽅向运动（实际是斜切向运动），每个磁头同⼀时刻也必须是同轴的，即从正上⽅向下看，所有磁头任何时候都是重叠的（不过⽬前已经有多磁头独⽴技术，可不受此限制）。
图7是磁盘结构的⽰意图。
图7
盘⽚被划分成⼀系列同⼼环，圆⼼是盘⽚中⼼，每个同⼼环叫做⼀个磁道，所有半径相同的磁道组成⼀个柱⾯。磁道被沿半径线划分成⼀个个⼩的段，每个段叫做⼀个扇区，每个扇区是磁盘的最⼩存储单元。为了简单起见，我们下⾯假设磁盘只有⼀个盘⽚和⼀个磁头。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上⽅，为了实现这⼀点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将⽬标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本⾝存取就⽐主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的⼏百分分之⼀，因此为了提⾼效率，要尽量减少磁盘I/O。为了达到这个⽬的，磁盘往往不是严格按需读取，⽽是每次都会预读，即使只需要⼀个字节，磁盘也会从这个位置开始，顺序向后读取⼀定长度的数据放⼊内存。这样做的理论依据是计算机科学中著名的局部性原理：
当⼀个数据被⽤到时，其附近的数据也通常会马上被使⽤。
程序运⾏期间所需要的数据通常⽐较集中。
由于磁盘顺序读取的效率很⾼（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提⾼I/O效率。
预读的长度⼀般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的⼤⼩相等的块，每个存储块称为⼀页（在许多操作系统中，页得⼤⼩通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发⼀个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会到数据的起始位置并向后连续读取⼀页或⼏页载⼊内存中，然后异常返回，程序继续运⾏。
B-/+Tree索引的性能分析mysql下载哪个盘
到这⾥终于可以分析B-/+Tree索引的性能了。
上⽂说过⼀般使⽤磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索⼀次最多需要访问h个节点。数据库系统的设计者巧妙利⽤了磁盘预读原理，将⼀个节点的⼤⼩设为等于⼀个页，这样每个节点只需要⼀次I/O就可以完全载⼊。为了达到这个⽬的，在实际实现B-Tree还需要使⽤如下技巧：
每次新建节点时，直接申请⼀个页的空间，这样就保证⼀个节点物理上也存储在⼀个页⾥，加之计算机存储分配都是按页对齐的，就实现了⼀个node只需⼀次I/O。
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差很多。
上⽂还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上⾯分析可以看到，d越⼤索引的性能越好，⽽出度的上限取决于节点内key和data的⼤⼩：
dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))
floor表⽰向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更⼤的出度，拥有更好的性能。
这⼀章从理论⾓度讨论了与索引相关的数据结构与算法问题，下⼀章将讨论B+Tree是如何具体实现为
MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍⾮聚集索引和聚集索引两种不同的索引实现形式。
MySQL索引实现
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现⽅式是不同的，本⽂主要讨论MyISAM和InnoDB两个存储引擎的索引实现⽅式。
MyISAM索引实现
MyISAM引擎使⽤B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。