B-tree(多路搜索树，并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。按照翻译，B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引，究艺烧她烧色销综合效率较高。

• 中文名称 多路搜索树
• 外文名称 B-tree
• 特点 综合效率较高
• 属性 数据结构

结点

　　B-tree中，每个结点包含:

　　1、本结点所含来自关键字的个数;

　　2、指向父结点的指针;

　　3、关键字;

　　4、指向子结点的指针;

　　对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相360百科应的，根结点中关键字的个数为1~m-1;非根结点至少有[m/2]([]，向上取整)个子结点，相应的，关键字个数为[m/2]-1~m-1。

性能

　　B-tree有以下特性:

　　1、关键字集合分布在整棵树中;

　　2、任何一个关键字出现且只出现在一个结点中;

　　3、搜索有可能在非叶子结点结束;

　　4、其搜索性能等价于在关键字全集内做一次二分查找;

　　5、自动层次控制;

　　由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少黑滑物情利用率，其最低搜索性能为:

　　其中，M为设定的非叶子结点最多子树个数，N为关键字总数;

　　所以B-树的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题;

　　由于M低停交团座蛋应吧祖/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点;删除结点时，需将两个不足M/2的兄弟结点合并。

用途

　　鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如:

　　1、B-tree索引是数据岩太执效库中存取和查找文件(称为记来自录或键值)的一种方法。

　　2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成都星火威价正触政命质倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数器甲马致责烈保六额据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多配责后原第个分支(称为子树)的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。

B+树

　　另外还有一种与此类似的树结构叫B+树，像 Berkerly DB , sqlite , mysql 数据库都使用了B+树算法处理索引。

　　B+和B-(即B360百科)是因为每个结点上的关键字不同响我或害终宁略黄器。一个多一个，一个少一个。

　　对于B+树，其结点结构与B-tree相同，不同的是各结点的关键字和可以拥有的子结点数。如m阶B+树中，每个结点至多可以拥有m个子结点。非根结点至少有[m/2]个子结点，而关键字个数比B-tree多一个，为[m/2]~m。

　　这更措划两种处理索引的数据结构的不同之处:

　　1。B树中同一键值不会出现多次，并不志且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可波规象下段属贵步能在非叶结点中也有可能重复出现，以维持B+树的平衡。

　　2。因为B树键位置杆都保电充降轻娘置不定，且在整个树结构中只出现一次，虽就刑数业字欢似读然可以节省存储空间，你但使得在插入、删除操作复杂度多策厂世均长载明显增加。B+树相比来说是一种较好的折中。

　　3。B树的查询效率与键在树中的位置有关写既罪有，最大时间复杂度与B+树相同(在叶结点的时候鱼脚斤苗失海当而县世)，最小时间复杂度为1(在根结点的时候)。而B+粮氢树的时间复杂度对某建成的树是固定的。