本文是博主学习了MySQL索引数据结构后的学习笔记，主要串联一下学习的模块，方便日后复习，更多内容请看MySQL索引背后的数据结构及算法原理。
本文主要介绍BTree的结构、主存和磁盘的不同、MySql不同引擎的索引。

数据结构及算法基础

索引

索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。
对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效。对于中到大型的表，索引就非常有效。但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。

索引的本质

MySQL官方对索引定义：索引（Index）是帮助MySQL高效获取数据的数据结构。

提取句子主干，就可以得到索引的本质：索引是数据结构。

索引的目的

索引是满足某种特定查找算法的数据结构，而这些数据结构会以某种方式指向数据，从而实现高效查找数据。

索引的作用

• 索引能够轻易将查询性能提升几个数量级。
  • 大大减少了服务器需要扫描的数据行数。
  • 帮助服务器避免进行排序和创建临时表（B+Tree 索引是有序的，可以用来做 ORDER BY 和 GROUP BY 操作）
  • 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，也就将相邻的数据都存储在一起）。

B-Tree和B+Tree

单纯从数据结构角度。

B-Tree

定义及特点

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]

• key为记录的键值，对于不同数据记录，key是互不相同的
• data为数据记录除key外的数据

d=2的B-Tree示意图

参数	意义
正整数d>1	度
正整数h	高度

那么B-Tree是满足下列条件的数据结构：

1. 所有叶节点具有相同的深度（树高h），也就是说 B-Tree 是平衡的
2. key和指针互相间隔，节点两端是指针
3. （节点内）一个节点中的 key 从左到右 非递减排列
4. （指向节点）如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于 keyi 且小于 keyi+1。
5. 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d
6. 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null
   (无论什么节点，指针数都不超过2d)

查，增删

• 按 key 检索数据

1. 从根节点进行二分查找
   1.1 如果找到则返回对应节点的 data
   1.2 否则对相应区间的指针指向的节点递归进行查找，直到找到节点(成功)或找到 null 指针(失败)，

• 插入删除
  由于插入删除新的数据记录会破坏 B-Tree 的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持 B-Tree 性质。

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

1. 每个节点的指针上限为2d而不是2d+1
2. 内节点不存储data，只存储key
3. 叶子节点不存储指针

B+Tree

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

增加了顺序访问指针的B+Tree

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率

为什么使用B-Tree（B+Tree）

索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。
这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

主存存取原理---RAM

模型

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里抛却具体差别，抽象一个简单存取模型来说明RAM的工作原理。

主存模型

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。

过程

当系统需要读取主存时，则：

1. 将地址信号放到地址总线上传给主存
2. 主存读到地址信号后，解析信号并定位到指定存储单元
3. 然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响。

磁盘存取原理---寻道、旋转

与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的

磁盘的整体结构示意图

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

一片磁盘

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时：

1. 系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区
2. 为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间
3. 然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

为什么要预读

• 磁盘存取速度远慢于主存
  由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。

预读的依据

• 局部性原理
  为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。

预读的作用

• 磁盘预读能提高I/O效率
  由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

如何预读

• 预读的长度一般为页（page）的整倍数
  页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+Tree索引优势

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B Tree 作为索引结构，主要有以下两个原因：

更少的检索次数

平衡树检索数据的时间复杂度等于树高 h，而树高大致为 O(h)=O(logdN)，其中 d 为每个节点的出度。

• BTree vs BRTree
  红黑树的出度为 2，而 B Tree 的出度一般都非常大。红黑树的树高 h 很明显比 B Tree 大非常多，因此检索的次数也就更多

• B+Tree vs B-Tree
  dmax=floor(pagesize/(keysize+datasize+pointsize))
  B+Tree 相比于 B-Tree 更适合外存索引，因为 B+Tree 内节点去掉了 data 域，因此可以拥有更大的出度，检索效率会更高

利用计算机预读特性

操作系统一般将内存和磁盘分割成固态大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。

• 数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点，并且可以利用预读特性，相邻的节点也能够被预先载入。
• 而红黑树由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性

MySQL索引实现

• 在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。
• B+ 树索引并不能找到一个给定键对应的具体值，它只能找到数据行对应的页，然后数据库把整个页读入到内存中，并在内存中查找具体的数据行

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

MyISAM索引原理图

如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

MyISAM辅助索引

MyISAM索引检索算法（非聚集索引）

1. 首先按照B+Tree搜索算法搜索索引
2. 如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录

MyISAM的索引方式也叫做非聚集的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

1. 数据文件本身就是索引文件

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构

• 这棵树的叶节点data域保存了完整的数据记录
• 这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引

InnoDB主索引（同时也是数据文件）

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引

因为InnoDB的数据文件本身要按主键聚集，所以

• InnoDB要求表必须有主键（MyISAM可以没有）
• 如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键
• 如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2. InnoDB的所有辅助索引都引用主键作为data域

InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

定义在Col3上的一个辅助索引

这里以英文字符的ASCII码作为比较准则。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

索引设计

• 主键不使用过长字段
  知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
• 主键不使用非单调字段
  用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

参考文章
MySQL索引背后的数据结构及算法原理
58沈剑