B树、B+树以及他们的应用
B树也是一种平衡树，不过不是二叉树。
B树查询的时间复杂度在log[M]N - log[2]N
B树 与 B+树
B树的定义：
- 跟节点的儿子数为[2, M]
- 除跟节点以外的非叶子节点的儿子数为[M/2, M].（M/2向上取整）
- 每个节点存放的关键字个数[M/2-1, M-1]. （这个也和儿子数相关，关键字个数=儿子数-1）
- 非叶子结点的关键字个数=指向儿子的指针个数-1
- 非叶子结点的关键字有序：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
- 所有叶子结点位于同一层
其中M表示这个B数的阶数
下面是一个B树插入的过程：
- B树的插入是从根节点开始的，当该节点膨胀到M+1的时候，节点会分裂，并推选出其父亲节点
- 新插入的节点总是根据路由，插入到相应的叶子节点中，如果叶子节点发生分裂，那么会将其中一个值推举到父亲(因为父节点下的字节点分裂，子节点增多，父节点分叉不够了，也需要增加关键字)，这时候就相当于将新的值插入到了父亲节点。
- B树的删除不算特别复杂，就相当于是插入的反过程，删除就相当于是合并(包括子节点间的合并和子父节点间的合并)
B+树的定义：
- 基本和B树一致
- 非叶子节点的指针个数和关键字相同
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）
- 为所有叶子节点增加一个链指针
- 所有的关键字全部会在叶子节点中出现
下面是一个B+树的插入过程：
B+的性质：
- 所有的节点都出现在叶子节点的链表中（稠密索引），而且链表中的关键字都是有序的。
- 不可能在非叶子节点中命中
- 非叶子节点相当于是 叶子结点的稀疏索引，叶子节点是转存关键字数据的数据层
- 更适合 文件索引系统(泛文件)
- 因为所有的key都出现在叶子节点，所以从跟节点开始的查询每一条数据的效率基本一样，比较稳定
通常在B+树上有两个头节点，一个指向跟节点，一个指向最小叶子节点。所以也有两种查询方式，一是从最小关键字开始顺序查找，二是从跟节点随机查找
ps: 还有一种树是B*树，它的非叶子节点的利用率更高
B树与B+树的应用
B+树通常用作数据的索引。
无论是数据库还是文件等，这些数据不像是我们运行的程序，所有的数据都是在内存里面，而内存的读取是很快的，只要能定位到数据的地址，就能很快的拿到数据，所以就算红黑树，或者扫描比较长的链表，数据多一点，也没关系，所以红黑树相比与链表，主要就在于解决了查询的次数，由N->lg[n]。
但是以文件形式存储的数据，比如数据库，文件等，他们不是在内存中，红黑树确实能降低查询次数，由于红黑树的父子节点是逻辑相邻，而不是物理相邻，使用红黑树降低了总体的查询次数，但是磁盘IO次数还是很高，用红黑树做索引，并不能降低磁盘IO的次数，而IO次数才是真正读取耗时的地方。所以引出了B树和B+树。
局部性原理与磁盘预读
磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。
为了减少磁盘IO，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这就是计算机科学中的的`局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用`**
读取呢也是有单位的，称做块(block)，每次读取通常是块的整数倍，一般呢块的大小为4K。通常用B/B+树结构存储的索引的节点都会设计为一个块的大小，这样一次IO就可以全部读入。
而B/B+树的非叶子节点只会存储记录中某个key作为索引的key，而不会存储整条记录，所以一个节点实际上可以存储很多的key(也就是树的阶，通常超过100)，所以树的阶实际也会非常大，所以树的深度就会很小(通常不会超过3)，所以B/B+树作为文件的索引是非常合适的。
数据库索引
在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引（叫这个名字，实际的技术和数据结构就是B+树）。
下面讨论两种存储引擎的索引存储方式：MyISAM和InnoDB
MyISAM
主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：
辅助索引（Secondary key）
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
我们通常称MyISAM的索引方式为非聚集索引
InnoDB
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同.
主键索引
在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
如图，InnoDB主索引同时也是数据文件。另外叶节点包含了完整的数据记录。这种索引叫做聚集索引。
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
InnoDB的辅助索引
InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能,但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。.
所以，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义 、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。
Linux 文件系统
请参考另一篇文章：linux文件系统
参考文献：
