之前说的2-3树，2-3-4树（与2-3树一样，只不过其可以有4结点，4结点包含小中大3个元素以及4个孩子，或没有孩子）都是B树的特例。对于B树来说，其实是一种平衡的多路查找树，结点最大的孩子数目成为B树的阶。（2-3树是3阶B树，2-3-4树是4阶B树）。
2-3-4树
对于一个m阶B树来说：
1、如果根节点不是叶子结点，其至少有两颗子树
2、每个非根的分支节点都有k-1个元素和k个孩子。每一个叶子结点n都有k-1个元素（ceil(m/2)=k=m，m为阶数，这里的m/2为向上取整。大家可以试着想想二叉树，就是m=2的时候，或者之前说的2-3树，m=3）。
3、所有叶子结点位于同一层次。
4、所有分支结点包含以下的信息数据，（n,A0,K1,A1,K2,A2,...,Kn,An），Ki(i=1,2,...,n)为关键字，且KiKi+1；Ai(i=0,1,2,...,n)为指向子树的指针，且指针Ai-1所指的子树中所有结点的关键字均小于Ki，An指向的子树中所有结点的关键字均大于Kn（n为关键字个数）
红色框框所代表的就是该结点有多少个元素（关键字），而K1=3，K2=5，K3=8就是父结点所代表的元素（关键字），至于A0，A1，A2，A3那就是指向子树的指针了，于是便有，Ai-1KiAi。
一、B树结构如何做到减少内存与外存交换数据的次数
对于B树结构来说，只需要对其结构进行调整，使得B树的阶数（或结点的元素）与硬盘存储的页面大小相匹配就可以。比如一颗阶的B树，1个结点包含个关键字，高度仅为2，它可以存储超10亿的关键字，我们只需要让根节点持久保存在内存中，那么这棵树寻找一个关键字只需要两次硬盘的读取即可。相对于二叉树的操作来说，B树减少了必须访问的结点和数据块的数量，从而提高了性能。B树结构就是为了内外存数据交互而准备的。
假设有1亿个结点，对于一个二叉平衡树来说，是log2(1亿)次=27次，如果1亿个结点都在内存中，27次显然不是问题，但问题是一亿个结点在内存中占多少内存，设一个结点是16位，那么一亿个结点就是1.5G，而数据库表里可不止一个。好的，内存放不下，我们放磁盘，但是磁盘计算是毫秒级的，多一次或者少一次，效率可能相差万倍。同样的16个叶子结点，但是二叉树与四阶B树的区别是很明显的，对于查找处于叶子结点的关键字，二叉树至少需要5次比较，而四阶B树只需要3次，
二、B树的查找性能
最坏的情况，对于一个n个关键字，m阶的B树来说（m2），第一层至少1个结点，第二层至少2个结点，除根节点外每个分支结点至少有ceil(m/2)棵子树，所以第三层至少有2*ceil[m/2]个结点，这样k+1层，至少有2*(ceil[m/2])^(k-1)个结点。若m阶B树有n个关键字，找到叶子结点时，相当于查找到不成功的结点为n+1，所以
n+1=2*[ceil(m/2)]^(k-1)
化简可得
k={log[ceil(m/2)][(n+1)/2]}+1
可以用特殊值法试试，一个3阶B树，一共3层，那么其节点至少是2^h-1=7个结点，元素值至少可以是ceil(3/2)-1=1，即至少是7个关键字，那么k={logceil(3/2)[(7+1)/2]}+1=(log24)+1=3，涉及到比较的结点数将不超过3。
三、B+树
对于B树结构来说，查找需要往返于每个结点之间，这就意味着需要在硬盘的页面之间进行多次的访问，如上图，需要对这棵B树遍历，需要从左1子结点-父节点-左2子节点-父节点-左3子节点-父节点-左4子节点。这父节点就一共被访问了3次，每次都会对结点中的元素进行一次遍历，非常糟糕。这样为了让遍历时每个元素只访问一次，在原有的B树结构基础上，加上了新的元素组织方式，将父节点中的关键字在分支结点中再次列出，并将所有的叶子结点都连接在一起，这就是B+树。
B+树是应文件系统所需而产生出来的B树变形树，多用于数据库和操作系统中。严格意义上讲，B+树不算树，在B+树中，分支结点中的元素会在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会有指向后一个叶子结点的指针。这样，对于从最小关键字开始查找的来说，只需要从左侧叶子结点开始往右找就可以了，如果想要找5~8之间的数，只要先找到5，然后往右找就可以了。
预览时标签不可点收录于话题#个上一篇下一篇