简介
在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binarysearchtree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
定义
B-Treeisaself-balancedsearchtreewithmultiplekeysineverynodeandmorethantwochildrenforeverynode.
B树是一种自平衡的搜索树,每一个节点node都有多个keys，并且每个节点有2个子节点或者多于2个子节点。
B+treeisanN-arytreewithavariablebutoftenlargenumberofchildrenpernode.AB+treeconsistsofaroot,internalnodesandleaves.Therootmaybeeitheraleaforanodewithtwoormorechildren
B+树是一个n叉排序树，通常每个节点有多个孩子，一棵B+树包含一个根节点、多个内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
特征
B-TreeofOrdermhasthefollowingproperties...
Property#1-Alltheleafnodesmustbeatsamelevel.Property#2-Allnodesexceptrootmusthaveatleast[m/2]-1keysandmaximumofm-1keys.Property#3-Allnonleafnodesexceptroot(i.e.allinternalnodes)musthaveatleastm/2children.Property#4-Iftherootnodeisanonleafnode,thenitmusthaveatleast2children.Property#5-Anonleafnodewithn-1keysmusthavennumberofchildren.Property#6-AllthekeyvalueswithinanodemustbeinAscendingOrder.
搜寻方法
InaB-Ttree,thesearchoperationissimilartothatofBinarySearchTree.InaBinarysearchtree,thesearchprocessstartsfromtherootnodeandeverytimewemakea2-waydecision(wegotoeitherleftsubtreeorrightsubtree).InB-Treealsosearchprocessstartsfromtherootnodebuteverytimewemaken-waydecisionwherenisthetotalnumberofchildrenthatnodehas.InaB-Ttree,thesearchoperationisperformedwithO(logn)time