B树

　　B树是为磁盘或其他存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但是在降低磁盘I/O方面表现很好。

　　B树和红黑树不同之处在于B树的节点可以有很多孩子，从数个到数千个。B树的严格高度可能比一棵红黑树的高度要小很多，因此可以使用B数在O(lgn)内完成一些动态集合的操作。

　　如果B树的一个内部节点x包含x.n个关键字，那么节点x就要x.n+1个孩子。节点x中的关键字就是分割点，它把节点x中所处理的关键字的属性分割为x.n+1个子域，每个子域都由x的一个孩子处理。当在一棵B树中查找一个关键字的时候，基于对存储在x中的x.n个关键字的比较，做出一个(x.n+1)路的选择。　　

　　对存储在磁盘上的一棵B树，通常分支因子在50-2000不等，具体取决于一个关键字相对于一页的大小，大的分支因子可以降低树的高度以及查找任何一个关键字所需的磁盘的存取次数。

B树的定义

一棵B树T是具有以下性质的有根树（树根表示为T.root）

 　　1.每个节点x具有下面的性质：

　　　　（1）x.n，当前存储在节点x中的关键字的个数；

　　　　（2）x.n个关键字本身x.key1，x.key2，...，x.keyn，以非降序排列，即x.key1 <= x.key2 <= ... <= x.keyn。

　　　　（3）x.leaf，一个布尔值，如果x是叶节点，则为true，否则为false。

　　2.每个内部节点x还包含x.n+1个指向孩子的指针x.c1,x.c2,...,x.cn+1，叶节点没有孩子，所以ci属性没有定义。

　　3.关键字x.keyi对存储在各自子树中关键字范围加以分割，如果ki为任意一个存储在以x.ci为根的子树中的关键字，那么

　　　　　　　　　　k1<=x.key1k2<=x.key2<=...<=x.key(x.n)<=kx.n+1

　　4.每个叶节点具有相同的深度，即数的高度h。

　　5.每个节点所包含的关键字个数有上界和下界，用一个被称为B树的最小度数（minmum degree）的固定整数t>=2来表示这些界。

B树的高度

B树上大部分操作所需的磁盘存取次数与B树的高度成正比。

查找元素的例子

　　如果查找数据29，那么首先会把硬盘块由磁盘加载到内存此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。 目前网站的访问速度限制都是在mysql上面，php虽然没有java的高，但是效率已经很高了，而mysql目前的负载都是集中在IO上面的，所以提高IO的速度都是提高了整个网站性能，有了索引大大的提高了mysql的执行效率。

数据库插入数据

首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

数据库删除数据