前言
我们都知道myIASM引擎和innoDB引擎,这两种引擎之所以不同主要是其数据结构的区别
B = blance
使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度
B-Tree
二叉查找树
什么是二叉查找树?
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
- 中序遍历就可以得到一个有序的序列
二叉查找树查找、插入的时间复杂度为 O(log n)
二叉查找
二分查找就是每次把搜索区域减少一半,时间复杂度是O(logN).
其优点是比较次数少，查找速度快，平均性能好；缺点是要求待查表为有序表，且插入删除困难
什么是B-Tree树
- 与二叉查找树、平衡二叉查找树、红黑树等二叉树形结构相比，B-Tree 是一种多路查找树。不像前者每个节点最多可以有两个孩子节点
- B-Tree 可以有许多子女，而且B树也可以在O(logn)时间内，实现各种如插入，删除等集合操作。更大的分支因子可以降低树的高度从而降低
- 频繁磁盘I/O读写所造成的查询效率低下。许多数据库系统都会使用B树或者B树的各种变形结构
- 数据结构如下:B-Tree 又叫平衡多路查找树。 一棵m阶的B-Tree有如下性质：
1
2
3
4
51.树中的每个节点最多含有m个孩子(m>=2)
2.除根节点和叶子节点外，其它每个节点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）
3.根结点至少有2个孩子，根节点同时是叶子节点除外
4.所有叶子结点都出现在同一层
5.内部节点至少半满
浅显易懂
假如：一本英文字典，单词+详细解释组成了一条记录，现在需要索引单词，那么以单词为key，单词+详细解释为data，B-Tree就是以一个二元组{key,data}来定义一条记录。如果一个节点有3条记录，那么会有对应的4个指针，用以指向下一个节点。B-Tree是有序且平衡的，所有叶子节点在同一层，即不会出现某个分支层级多，某个分支层级少的情况
一颗B-Tree树
B-Tree树的特点
根据他的数据结构我们可以看出它有一些特性:1
2
3
4
5
61.保持键值有序，以顺序遍历
2.使用层次化的索引来最小磁盘读取
3.使用不完全填充的块来加速插入和删除
4.通过优雅的遍历算法来保持索引平衡
5.通过保证内部节点至少半满来最小化空间浪费
6.一棵树可以处理任意数目的插入和删除
B+-Tree
B+ -Tree是B-Tree的一个变种。那么它们有什么不一样呢（同为m阶）：
- 叶子节点存储了所有的关键字信息
- 叶子节点的最后一个指针指向相邻的下一个叶子节点
我们来看两张图就能体会区别所在了
再来一张
B+的特性
- 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；我们从第一张图很好的看出来这一点
- 不可能在非叶子结点命中；
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
- 更适合文件索引系统；(这个后面解释)
数据库为什么用B-Tree树(B+Tree)
首先简单讲一些概念
读内存和读磁盘
读内存和读磁盘效率差距很大
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数
磁盘存储原理
磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
分析
上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。
看下面的图: 一个节点就是一页
为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
综上所述，用B-Tree作为索引结构效率是非常高的。
MyISAM与B+Tree
MyISAM引擎使用的是B+Tree作为索引结构,叶节点的data域存放的数据记录的地址
MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
InnoDB与B+Tree
虽然innoDB也使用B+Tree作为索引结构,但是实现却和myISAM不同
- MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引
可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。 - InnoDB的辅助索引data域存储相应记录主键的值而不是地址,换句话说，InnoDB的所有辅助索引都引用主键作为data域(辅助索引就是非主键的索引)
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
比较
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。