B树与数据库索引

> B树是为了磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但是在降低磁盘IO操作数方面要更好一些。B树与红黑树的不同之处在于B树的结点可以有很多孩子。从几个到几千个都可以。和红黑树一样，有n个结点的B树的高度为O(lgn),然而一个b树的严格高度可能比一颗红黑树要小许多。这就是因为他的分支因子。表示高度的对数的底数可以非常大。

在了解B树之前先必须要弄明白磁盘存储的数据结构和随机访问的主存数据结构的不同。

##1. 磁盘存储数据结构
    一个典型的磁盘驱动器，它包括了n个绕主轴旋转的盘片，每个盘片通过磁臂末端的磁头来读写。这些磁臂围绕着一个共同的旋转轴旋转。当读写磁头静止时，它下方经过的磁盘表面就是一个磁道。磁盘的机械运动相比主存来说是非常慢的。目前磁盘的旋转速度在5400-15000转/分钟。服务器级别（15kRPM），台式机（7200RPM），笔记本（5400RPM）。对台式机来说，旋转一周需要8.33ms。每次读出多个页面。
![磁盘驱动器][1]
    
    在一个典型的B树应用中，所要处理的数据量非常大，所有数据无法一次装入内存中。b树算法通常只会在主存中保留一定数量的页面。对我们来说，一颗B树中保存所有的数据那是最好的，因此，一个B树的结点通常和一个完整的磁盘页一样大。磁盘页大小限制了B树结点的孩子个数。一般磁盘中一个大的b树，分支因子在50-2000之间。具体取决于页面大小。一个大的分支因子，可以大大降低树的高度以及查找一个关键字所需的磁盘存取次数。
![此处输入图片的描述][2]
在图中的一个分支因子为1001，高度为2的B树，他可以存储超过10亿个关键字。这棵树查找任何一个关键字，至多需要两次磁盘操存取。

##2. B树的定义
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
> 1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。
B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）
其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

##3. B+树
B+树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B+树和m 阶的B-
树的差异在于：
⑴有n 棵子树的结点中含有n 个关键码；
⑵所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。
 如图一棵3阶的B+树:
 ![此处输入图片的描述][3]
通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找。 
在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+
树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

##4. MySql中B-Tree应用
在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型

###4.1 MyISAM索引实现：
1. 主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：
![此处输入图片的描述][4]

MyISAM的索引文件仅仅保存数据记录的地址。

2. 辅助索引（Secondary key）
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
![此处输入图片的描述][5]
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
###4.2. InnoDB索引实现
然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同.

1）主键索引：

    MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
    
2）. InnoDB的辅助索引

    InnoDB的所有辅助索引都引用主键作为data域。
    
   InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义 、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。
      文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

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

 InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

----

参考链接 ： http://blog.csdn.net/hguisu/article/details/7786014

  [1]: http://www.cas.cn/kxcb/kpwz/201105/W020110530320191787759.jpg
  [2]: http://res.chuang.ba/btree.png
  [3]: http://my.csdn.net/uploads/201207/28/1343448307_6771.jpg
  [4]: http://my.csdn.net/uploads/201208/01/1343757655_1008.png
  [5]: http://my.csdn.net/uploads/201208/01/1343757949_9784.png​