【数据结构】B树/B+树

前端之家收集整理的这篇文章主要介绍了【数据结构】B树/B+树前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

本篇博文旨在介绍一种适合外查找的树---B树,以及B树的延伸B+树;比较了B树和B+树的各自优缺点;说明了B树B+树的应用场景;以及实现了B树的代码


B树

B树的概念和性质

B树是一种适合外查询的树,它是一种多叉平衡树

除此之外,它还满足如下的性质:

(1)根节点有至少两个孩子

(2)非根节点的孩子数量在【M/2,M】之间

(3)每个节点的key值的数量在【(M/2) - 1,M-1】之间,关键字并按照升序排序

(4)所有的叶子节点均在同一层

(5)key[i],key[i+1],这两个关键值之间的孩子的值在key[i]到key[i+1]之间

一颗M=3的B树


B树节点的定义

//定义B树的节点
template<typename K,typename V,size_t M = 3>
struct BTreeNode
{
	pair<K,V> _kv[M];
	
	BTreeNode<K,V> *_subs[M+1];
	BTreeNode<K,V> *_parent;

	//表示存储了多少个Key值
	size_t _size;

	//节点的构造函数
	BTreeNode()
		:_size(0),_parent(NULL)
	{
		for (size_t i = 0; i <= M; ++i)
		{
			_subs[i] = NULL;
		}
	}
};
我们按照B树的概念及其性质定义了如上的节点类

B树如何查找一个key值

	//查找函数,其返回值的设计实现了Insert的复用
	pair<Node*,int> Find(const K& key)
	{
		//若查询不到,则用parent记录需要插入的节点的父节点
		//实现了Insert的复用
		Node* cur = _root;
		Node* parent = NULL;

		while (cur)
		{
			size_t index = 0;
			while (index < cur->_size)
			{
				if (key > cur->_kv[index].first)
				{
					index++;
				}
				else if (key == cur->_kv[index].first)
				{
					//查询到,返回查询的节点
					return make_pair(cur,index);
				}
				else
				{
					break;
				}
			}
			parent = cur;
			cur = cur->_subs[index];
		}

		//没有查询到,返回需要插入节点的父亲节点
		//实现了Insert函数的复用
		return make_pair(parent,-1);
	}
这里和搜索树的方式相同,只是由于定义的不同而实现的略有区别而已,概念都是一样的

这里使用了pair,pair是一个结构体类型,返回值返回的是节点的指针以及查找成功与否的bool

B树的插入方法

插入的时候可能遇到以下情况:

(1)B树为空

创造新节点,并给根赋值

(2)插入的时候,B树已经存在了该Key值

根据find返回值pair结构体的第二个参数,可以判断原B树是否存在对应的Key值

若存在,则插入失败;

否则再插入

(3)插入一个节点后,该节点未满

插入完成,直接返回TRUE

(4)插入一个节点后,该节点的关键值满了,需要分裂

分裂方法

将该节点的右半区间移到一个新的节点中(移动时也要把孩子移过去)

生成节点后,还要注意之前有没有父亲节点;

若没有,就需要将中间的元素提到新的根节点;

(5)分裂时,若分裂的节点有父亲节点

这种情况可能继续调整,因为之前分裂会将一个key值给父亲节点

父亲节点的key值数量+1,也就有可能满了


上面的情况是分裂节点为空的情况,不用继续调整,就可结束

代码中有对所有情况的分析和注释

	bool Insert(const pair<K,V>& kv)
	{
		//情况1.当根节点为空的时候,需要对_root进行赋值
		if (_root == NULL)
		{
			_root = new Node;
			_root->_size = 1;
			_root->_kv[0] = kv;
			return true;
		}

		//情况2.不为空,则找到插入的位置
		//如果second的值不为-1,则表示已经存在,不需要插入
		pair<Node*,int> ret = Find(kv.first); 
		if (ret.second != -1)
			return false;

		//进行插入
		Node* cur = ret.first;
		Node* temp = cur;
		pair<K,V> newKV = kv;
		Node* sub = NULL;

		while (1)
		{
			//在cur节点插入kv和sub
			_Insert(cur,newKV,sub);

			//情况3.如果cur没满,则表示插入成功
			//否则需要进行分裂
			if (cur->_size < M)
				return true;

			//情况4.构造一个新节点tmp
			Node* tmp = new Node;
			size_t mid = M >> 1;
			size_t i = mid+1;
			size_t j = 0;

			//将右半区间的元素移到tmp中
			while (i < cur->_size)
			{
				tmp->_kv[j] = cur->_kv[i];
				cur->_kv[i] = pair<K,V>();

				tmp->_subs[j] = cur->_subs[i];
				if (cur->_subs[i])
					cur->_subs[i]->_parent = tmp;

				//调整
				i++;
				j++;
				tmp->_size++;
				cur->_size--;
			}

			//拷走最后一个右孩子
			tmp->_subs[j] = cur->_subs[i];
			cur->_subs[i] = NULL;
			if (cur->_subs[i])
				cur->_subs[i]->_parent = tmp;

			//情况5.如果cur没有父亲节点,需要创建
			//如果cur有父亲节点,那么需要将中间元素插入到父亲节点里
			if (cur->_parent)
			{
				//继续向上调整,判别是否parent会满
				newKV = cur->_kv[mid];
				sub = tmp;
				cur->_size--;
				cur = cur->_parent;
			}
			else
			{
				//定义一个新根节点,将中间元素放入该节点中
				Node* newRoot = new Node;
				newRoot->_kv[0] = cur->_kv[mid];
				newRoot->_size = 1;

				//设置新根节点的两个孩子cur和tmp
				//并修改他们的父亲节点
				newRoot->_subs[0] = cur;
				cur->_parent = newRoot;
				newRoot->_subs[1] = tmp;
				tmp->_parent = newRoot;

				cur->_size--;

				//将根节点重新赋值
				_root = newRoot;
				return true;
			}
		}
	}

B树的代码实现

#pragma once

#include<iostream>
using namespace std;

/*
* author:haohaosong
* date:2017/2/23
* note:B树的实现 
*/

//B树的增删查改的时间复杂度 O(logM(N))

//定义B树的节点
template<typename K,_parent(NULL)
	{
		for (size_t i = 0; i <= M; ++i)
		{
			_subs[i] = NULL;
		}
	}
};

//B树的定义
template<typename K,size_t M = 3>
class BTree
{
	typedef BTreeNode<K,V> Node;
public:
	//构造函数
	BTree()
		:_root(NULL)
	{}

	//查找函数,其返回值的设计实现了Insert的复用
	pair<Node*,-1);
	}

	bool Insert(const pair<K,V>& kv)
	{
		//当根节点为空的时候,需要对_root进行赋值
		if (_root == NULL)
		{
			_root = new Node;
			_root->_size = 1;
			_root->_kv[0] = kv;
			return true;
		}

		//不为空,则找到插入的位置
		//如果second的值不为-1,则表示已经存在,不需要插入
		pair<Node*,sub);

			//如果cur没满,则表示插入成功
			//否则需要进行分裂
			if (cur->_size < M)
				return true;

			//构造一个新节点tmp
			Node* tmp = new Node;
			size_t mid = M >> 1;
			size_t i = mid+1;
			size_t j = 0;

			//将右半区间的元素移到tmp中
			while (i < cur->_size)
			{
				tmp->_kv[j] = cur->_kv[i];
				cur->_kv[i] = pair<K,V>();

				tmp->_subs[j] = cur->_subs[i];
				if (cur->_subs[i])
					cur->_subs[i]->_parent = tmp;

				//调整
				i++;
				j++;
				tmp->_size++;
				cur->_size--;
			}

			//拷走最后一个右孩子
			tmp->_subs[j] = cur->_subs[i];
			cur->_subs[i] = NULL;
			if (cur->_subs[i])
				cur->_subs[i]->_parent = tmp;

			//如果cur没有父亲节点,需要创建
			//如果cur有父亲节点,那么需要将中间元素插入到父亲节点里
			if (cur->_parent)
			{
				//继续向上调整,判别是否parent会满
				newKV = cur->_kv[mid];
				sub = tmp;
				cur->_size--;
				cur = cur->_parent;
			}
			else
			{
				//定义一个新根节点,将中间元素放入该节点中
				Node* newRoot = new Node;
				newRoot->_kv[0] = cur->_kv[mid];
				newRoot->_size = 1;

				//设置新根节点的两个孩子cur和tmp
				//并修改他们的父亲节点
				newRoot->_subs[0] = cur;
				cur->_parent = newRoot;
				newRoot->_subs[1] = tmp;
				tmp->_parent = newRoot;

				cur->_size--;

				//将根节点重新赋值
				_root = newRoot;
				return true;
			}
		}
	}

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
protected:
	void _Insert(Node* cur,const pair<K,V>& newKV,Node* sub)
	{
		//这里要用int,不能用size_t,会影响while循环的判断条件
		int index = (cur->_size)-1;
		while (index >= 0)
		{
			//找到合适的插入位置,跳出
			if (newKV.first > cur->_kv[index].first)
				break;

			//将key值向后移动,并且将孩子也移动
			cur->_kv[index + 1] = cur->_kv[index];
			cur->_subs[index + 2] = cur->_subs[index + 1];
			index--;
		}

		//插入新的KV以及孩子
		cur->_kv[index+1] = newKV;
		cur->_subs[index+2] = sub;

		//孩子存在,给其父亲赋值
		if (sub)
			sub->_parent = cur;

		cur->_size++;
	}

	//中序遍历递归函数
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		//访问每一个key值及其左孩子
		size_t index = 0;
		while (index < root->_size)
		{
			_InOrder(root->_subs[index]);
			cout << root->_kv[index].first<<" ";
			index++;
		}

		//打印最后一个key值的右孩子
		_InOrder(root->_subs[root->_size]);
	}
protected:
	Node* _root;
};

void TestBtree()
{
	BTree<int,int> t;
	int a[] = { 53,75,139,49,145,36,101 };
	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		t.Insert(make_pair(a[i],i));
		t.InOrder();
	}

	t.InOrder();
}

B+树

B树的特点

B+树是B树的一种变形树,它的基本特性和B树一致

只是有下列区别:

(1)每个节点的key值和子节点的个数对应

(2)非叶子节点只是起到索引的作用,只有叶子节点内部存储数据

(3)所有的叶子节点由一个链表串起来,并且是有序的,可以根据关键值的次序遍历全部记录


B树和B+树的对比

B树的优点:

和B+树相比,每一个节点都有key和对应的value,如果访问的元素离根节点较近,则访问很迅速

B+树的优点:

(1)叶子节点是用链表串起来的,遍历一遍的速度很快;相反如果采用B树,则需要遍历整颗树

(2)B+树的数据是顺序排列的,并且是相连的所以在区间内查找时(比如查找成绩在70~80分之间的学生),B+树很方便就可以办到

而如果采用B树,B树要对每一层递归的进行遍历,效率低;

(3)空间局部性高,缓存命中率高

B树和B+树的主要应用:

它们主要运用在文件存储系统以及数据库系统中

一些主流的数据库,如MysqL,Oracle对B数,B+树都有运用

当然是进行优化过后的

原文链接:https://www.f2er.com/datastructure/382337.html

猜你在找的数据结构相关文章