大佬教程收集整理的这篇文章主要介绍了【数据结构】对B树的认识，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
二叉搜索树、平衡二叉树、红黑树都是我们之前学过的典型的二叉搜索树，其查找的时间复杂度和树的高度都是O(log2N)。
但是如果我们的数据量很大的话，比如像文件系统及数据库系统普遍都采用B-/+树作为索引结构。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O的消耗，相信大家都知道，相比于内存存取，I/O操作的消耗会更大，因此，我们需要尽量减少查找过程中磁盘I/O的存取次数。
如果使用红黑树的结构，当然也可以达到目的，但这样的缺点是数据量大，树的高度太高，访问磁盘的次数增加，从而效率低下。
B树也可以写作B-树（但不可以读成“B减树”，这样是不对的），它是一种平衡的多叉树。定义如下：
一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：
1. 根节点至少有两个孩子
2. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
3. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字，并且以升序排列
4. keY[i]和keY[i+1]之间的孩子节点的值介于keY[i]、keY[i+1]之间
5. 所有的叶子节点都在同一层
如下图所示:
B树的插入需要在叶子结点处插入，当结点中的关键字满时，需要做分裂操作。为方便实现操作，我们在定义结点的时候多定义一个关键字和指针。举一个例子：在下面这个树中插入101这个数字。
总结一下：
1. 找插入位置（如果找到了，则不必再插入）
2. 将元素插入找到的位置（使用插入排序的思想）
3. 检测当前结点是否满足性质，关键字至多M-1个，如果不满足该性质，则需要将该结点分裂
4. 分裂：找中间位置，将中间位置以后的元素全部搬移到新结点（孩子结点比关键字多搬移一个），如果当前结点不是根结点，那么将中间元素搬移到当前结点的双亲，看双亲结点是否满足性质，继续循环；如果当前结点是根结点，则需要再将根结点分裂一次
B+树与B树基本相同，区别在于B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找。
B+树的特性：
1. 所有的关键字都出现在非叶子结点的链表中，且链表中的关键字恰好是有序的
2. 不可能在飞叶子结点命中
3. 非叶子结点相当于是叶子结点的索引，叶子结点相当于是存储数据的数据层
4. 更适合文件索引系统、
下面是B树具体的结构及插入操作，在此我将M默认设置为3，也可以修改为其他的值
#include <iostream>
using namespace std;
template <class K,int M=3>
struct BTreeNode
{
BTreeNode()
: _pParent(NULL),_size(0)
{
for (size_t i = 0; i <= M; i++)
_pSub[i] = NULL;
}
K _keY[R_358_11845@];
BTreeNode<K,M>* _pSub[M + 1];
BTreeNode<K,M>* _pParent;
size_t _size;
};
template <class K,int M=3>
class BTree
{
typedef BTreeNode<K,M> Node;
typedef Node* PNode;
public:
BTree()
: _pRoot(NULL)
{}
bool Insert(K& key)
{
if (_pRoot == NULL)//根结点直接插入
{
_pRoot = new Node();
_pRoot->_keY[0] = key;
_pRoot->_size = 1;
return true;
}
pair<PNode,int> ret = Find(key);
if (ret.second >= 0)//没找到才需要插入结点
return false;
PNode pCur = ret.first;
PNode pSub = NULL;
while (1)
{
_InsertKey(pCur,key,pSub);//插入结点
int size = pCur->_size;
if (size < M)//插入成功，不需要分裂
return true;
else
{
int mid = size >> 1;
PNode temp = new Node();
for (size_t i = mid + 1; i < size; i++)//分裂 搬移结点中的key和孩子结点
{
temp->_keY[temp->_size] = pCur->_keY[i];
temp->_pSub[temp->_size] = pCur->_pSub[i];
if (temp->_pSub[temp->_size])
temp->_pSub[temp->_size]->_pParent = temp;
temp->_size++;
}
temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size];
if (temp->_pSub[temp->_size])
temp->_pSub[temp->_size]->_pParent = temp;
pCur->_size -= (temp->_size + 1);//处理size
if (pCur == _pRoot)//如果当前结点是根结点，还需要再处理
{
_pRoot = new Node;
_pRoot->_keY[0] = pCur->_keY[R_358_11845@id];
_pRoot->_pSub[0] = pCur;
pCur->_pParent = _pRoot;
_pRoot->_pSub[1] = temp;
temp->_pParent = _pRoot;
_pRoot->_size = 1;
return true;
}
else
{
key = pCur->_keY[R_358_11845@id];
pCur = pCur->_pParent;
pSub = temp;
}
}
}
}
pair<PNode,int> Find(const K& key)//查找值为key的结点，找到返回结点及在结点中的位置，没找到返回当前结点的双亲结点及-1
{
PNode pCur = _pRoot;
PNode pParent = NULL;
while (pCur)
{
int i = 0;
while (i < pCur->_sizE)
{
if (key == pCur->_keY[i])
return pair<PNode,int>(pCur,i);
else if (key < pCur->_keY[i])
break;
else
i++;
}
pParent = pCur;
pCur = pCur->_pSub[i];
}
return make_pair(pParent,-1);//没找到返回-1
}
void InOrder()
{
_InOrder(_pRoot);
}
private:
void _InsertKey(PNode pCur,const K& key,PNode pSub)
{
//直接插入的思想
int end = pCur->_size - 1;
while (key < pCur->_keY[end] && end >= 0)
{
pCur->_keY[end + 1] = pCur->_keY[end];
pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
end--;
}
pCur->_keY[end + 1] = key;
pCur->_pSub[end + 2] = pSub;
if (pSub)
pSub->_pParent = pCur;
pCur->_size += 1;
}
void _InOrder(PNode pRoot)
{
if (pRoot == NULL)
return;
for (size_t i = 0; i < pRoot->_size; i++)
{
_InOrder(pRoot->_pSub[i]);
cout << pRoot->_keY[i] << " ";
}
_InOrder(pRoot->_pSub[pRoot->_size]);
}
private:
PNode _pRoot;
};
void test()
{
int arr[] = { 53,75,139,49,145,36,101 };
BTree<int> b;
size_t size = sizeof(arr) / sizeof(arr[0]);
for (size_t i = 0; i < 7; i++)
{
b.Insert(arr[i]);
b.InOrder();
cout << endl;
}
}
以上是大佬教程为你收集整理的【数据结构】对B树的认识全部内容，希望文章能够帮你解决【数据结构】对B树的认识所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。