B树的介绍及其实现
B树的介绍及其实现
一、B树的基本概念
为什么要引入B树
在学习过的数据结构中，如：AVL树、红黑树和哈希表等都具有很好的查找效率，但是只能适用于数据量不大的情况下。如果数据量很大时，这些数据不能够一次性的存入内存中，那么在进行查找的时候，就需要多次的访问IO，这样的速度是非常的慢的，此时就引入了BTree这个结构。我们只需要将关键字和其映射的数据的地址放到内存中的BTree中，就可以很快的定位到数据的地址，然后去磁盘中查找了。
1.1 B树的概念
B树是一种适合外查找的树，它是一种平衡的多叉树，称为B树 。B树的特点：
- 根节点至少有两个孩子
- 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
- 每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m
- 所有的叶子节点都在同一层
- 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划 分
- 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键 字，且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。
二、B树的实现
2.1 B树的定义
根据B树的特点，需要定义存放key值的数组、指向孩子节点的指针数组、父节点指针、key个数：
其中M使用的是非类型模板参数，只能为整数。
template<class T, size_t M>
struct BTreeNode {
typedef BTreeNode<T, M> node;
T _keys[M]; //存放数值
node* _subs[M + 1]; //存放孩子节点
node* _parent; //父节点
size_t _n; //key的个数
BTreeNode() {
for (int i = 0; i < M; ++i) {
_keys[i] = T();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};
2.2 B树的查找
- 如果key小于当前遍历到的节点的值，就访问它的左孩子节点
- 如果key大于当前遍历到的节点的值，就在当前节点往后遍历_keys数组
- 如果相等，那么返回该节点的地址和其所在_keys数组中的下标
pair<Node*, int> Find(const T& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
size_t i = 0;
while (i < cur->_n) {
if (key < cur->_keys[i]) {
break;
}
else if (key > cur->_keys[i]) {
++i;
}
else {
return make_pair(cur, i);
}
}
parent = cur;
cur = cur->_subs[i];
}
return make_pair(parent, -1);
}
2.3 B树的插入
使用{53, 139, 75, 49, 145，36}构建B树的过程如下所示：
- 刚开始插入53和139：
- 插入75：
- 插入36：
通过上述的观察可得出：
- 如果树为空，创建一个新节点作为根节点，然后直接插入
- 如果树不为空，找到要插入的位置，然后插入
- 插入后检查节点是否满足B树的性质，满足就不需要处理
- 如果不满足，将需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 判断父节点是否为空，如果为空就创建一个新节点作为父节点，然后将中间位置的元素插入到父节点中，如果父节点不为空，那么就直接插入到父节点中。最后将他们相连
//插入排序插入数据
void InsertKey(Node* cur, const T& key, Node* child) {
//使用插入排序的方式，将元素向后移动
int end = cur->_n - 1;
while (end >= 0) {
if (key < cur->_keys[end]) {
cur->_keys[end + 1] = cur->_keys[end];
cur->_subs[end + 2] = cur->_subs[end + 1];
--end;
}
else {
break;
}
}
//当key >= cur->_keys[end]时，将key插入
cur->_keys[end + 1] = key;
cur->_subs[end + 2] = child;
if (child) {
child->_parent = cur;
}
++cur->_n;
}
bool insert(const T& key) {
//如果root为空，创建一个节点，直接插入
if (!_root) {
_root = new Node();
_root->_keys[0] = key;
++_root->_n;
return true;
}
//判断树中是否存在该key，存在就不插入了
pair<Node*, int> ff = Find(key);
if (ff.second >= 0)return false;
//不存在就进行插入操作
Node* cur = ff.first;
T newkey = key;
Node* child = nullptr;
while (true) {
InsertKey(cur, newkey, child);
//插入后对节点进行检查
if (cur->_n < M) {
return true;
}
else {
//进行分裂操作
size_t mid = cur->_n / 2;
Node* brother = new Node();
size_t i = mid + 1;
size_t j = 0;
//将cur中的1/2移动到他的兄弟节点
while (i < cur->_n) {
brother->_keys[j] = cur->_keys[i];
brother->_subs[j] = cur->_subs[i];
if (cur->_subs[i]) {
cur->_subs[i]->_parent = brother;
}
cur->_keys[i] = T();
cur->_subs[i] = nullptr;
++i, ++j;
}
brother->_subs[j] = cur->_subs[i];
if (cur->_subs[i]) {
cur->_subs[i]->_parent = brother;
}
cur->_subs[i] = nullptr;
brother->_n = j;
//因为移走了n个到brother中，还有一个要移到父节点中，所以多-1
cur->_n -= brother->_n + 1;
T midkey = cur->_keys[mid];
cur->_keys[mid] = T();
//如果cur没有父节点，那么就创建
if (!cur->_parent) {
_root = new Node();
cur->_parent = _root;
brother->_parent = _root;
_root->_keys[0] = midkey;
_root->_subs[0] = cur;
_root->_subs[1] = brother;
_root->_n = 1;
break;
}
else {
//有父节点，将插入排序插入的参数修改，使用上述的逻辑进行插入
newkey = midkey;
child = brother;
cur = cur->_parent;
}
}
}
}
2.4 B树的删除
B树的删除分为3种情况：
- 直接删除关键字：若删除当前关键字后仍然满足B树定义，则直接删除该关键字。
- 兄弟够借：若再删除一个关键字就会破坏B树定义，并且左，右兄弟的关键字个数大于等于ceil(m/2)，则需要调整该结点、右（或左）兄弟结点及其父结点（父子换位法），以达到新的平衡。
- 兄弟不够借：若左、右兄弟结点的关键字个数都不足以被借，则将关键字删除后与左（或右）兄弟结点及父结点的关键字进行合并。
由于B树的删除用代码实现非常复杂，这里就不实现了。
2.5 B树的前序遍历
使用循环遍历节点孩子数组，先访问左孩子，再访问右孩子。
//前序遍历子函数
void _InOrder(Node* cur) {
if (!cur)return;
size_t i = 0;
while (i < cur->_n) {
_InOrder(cur->_subs[i]);
cout << cur->_keys[i] << " ";
++i;
}
_InOrder(cur->_subs[i]);//遍历每个节点中的最后一个孩子
}
//前序遍历
void InOrder() {
_InOrder(_root);
}
三、测试创建的B树是否正确
void TestBtree()
{
int a[] = { 53, 139, 75, 49, 145, 36, 101 };
BTree<int, 3> t;
for (auto e : a)
{
t.insert(e);
}
t.InOrder();
}
最终结果如果是有序的，那么就是正确的。这就不演示了。
四、B树的性能分析
- 对于一棵节点为N度为M的B-树，查找和插入需要log{M-1}N~log{M/2}N次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要 log{M-1}N 和 log{M/2}N之间，在定位到该节点后，再采用二分查找的方式可以很快的定位 到该元素。
- B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则log_{M/2}N <= 4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用 二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。
五、全部代码
#include<iostream>
using namespace std;
template<class T, size_t M>
struct BTreeNode {
typedef BTreeNode<T, M> node;
T _keys[M]; //存放数值
node* _subs[M + 1]; //存放孩子节点
node* _parent; //父节点
size_t _n; //key的个数
BTreeNode() {
for (int i = 0; i < M; ++i) {
_keys[i] = T();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};
template<class T, size_t M>
class BTree {
typedef BTreeNode<T, M> Node;
public:
BTree()
:_root(nullptr)
{}
pair<Node*, int> Find(const T& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
size_t i = 0;
while (i < cur->_n) {
if (key < cur->_keys[i]) {
break;
}
else if (key > cur->_keys[i]) {
++i;
}
else {
return make_pair(cur, i);
}
}
parent = cur;
cur = cur->_subs[i];
}
return make_pair(parent, -1);
}
bool insert(const T& key) {
//如果root为空，创建一个节点，直接插入
if (!_root) {
_root = new Node();
_root->_keys[0] = key;
++_root->_n;
return true;
}
//判断树中是否存在该key，存在就不插入了
pair<Node*, int> ff = Find(key);
if (ff.second >= 0)return false;
//不存在就进行插入操作
Node* cur = ff.first;
T newkey = key;
Node* child = nullptr;
while (true) {
InsertKey(cur, newkey, child);
if (cur->_n < M) {
return true;
}
else {
//进行分裂操作
size_t mid = cur->_n / 2;
Node* brother = new Node();
size_t i = mid + 1;
size_t j = 0;
//将cur中的1/2移动到他的兄弟节点
while (i < cur->_n) {
brother->_keys[j] = cur->_keys[i];
brother->_subs[j] = cur->_subs[i];
if (cur->_subs[i]) {
cur->_subs[i]->_parent = brother;
}
cur->_keys[i] = T();
cur->_subs[i] = nullptr;
++i, ++j;
}
brother->_subs[j] = cur->_subs[i];
if (cur->_subs[i]) {
cur->_subs[i]->_parent = brother;
}
cur->_subs[i] = nullptr;
brother->_n = j;
//因为移走了n个到brother中，还有一个要移到父节点中，所以多-1
cur->_n -= brother->_n + 1;
T midkey = cur->_keys[mid];
cur->_keys[mid] = T();
//如果cur没有父节点，那么就创建
if (!cur->_parent) {
_root = new Node();
cur->_parent = _root;
brother->_parent = _root;
_root->_keys[0] = midkey;
_root->_subs[0] = cur;
_root->_subs[1] = brother;
_root->_n = 1;
break;
}
else {
//有父节点，将插入排序插入的参数修改，使用上述的逻辑进行插入
newkey = midkey;
child = brother;
cur = cur->_parent;
}
}
}
}
//前序遍历
void InOrder() {
_InOrder(_root);
}
private:
//插入排序插入数据
void InsertKey(Node* cur, const T& key, Node* child) {
//使用插入排序的方式，将元素向后移动
int end = cur->_n - 1;
while (end >= 0) {
if (key < cur->_keys[end]) {
cur->_keys[end + 1] = cur->_keys[end];
cur->_subs[end + 2] = cur->_subs[end + 1];
--end;
}
else {
break;
}
}
//当key >= cur->_keys[end]时，将key插入
cur->_keys[end + 1] = key;
cur->_subs[end + 2] = child;
if (child) {
child->_parent = cur;
}
++cur->_n;
}
//前序遍历
void _InOrder(Node* cur) {
if (!cur)return;
size_t i = 0;
while (i < cur->_n) {
_InOrder(cur->_subs[i]);
cout << cur->_keys[i] << " ";
++i;
}
_InOrder(cur->_subs[i]);//遍历每个节点中的最后一个孩子
}
Node* _root;
};
void TestBtree()
{
int a[] = { 53, 139, 75, 49, 145, 36, 101 };
BTree<int, 3> t;
for (auto e : a)
{
t.insert(e);
}
t.InOrder();
}
六、B+树和B*树
6.1 B+树
B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又 在B树的基础上做了以下几点改进优化：
- 分支节点的子树指针与关键字个数相同
- 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
- 所有叶子节点增加一个链接指针链接在一起
- 所有关键字及其映射数据都在叶子节点出现
B+树的特性：
- 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
- 不可能在分支节点中命中。
- 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。
B+树的分裂： 当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增 加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向 兄弟的指针。
6.2 B*树
B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
B树的分裂： 当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结 点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如 果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父 结点增加新结点的指针。 所以，B树分配新结点的概率比B+树要低，空间使用率更高；
总结
B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B*树：一棵更丰满的，空间利用率更高的B+树。
七、B树的应用
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如： 书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价 值的分类网站，本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说： 索引就是数据结构。
当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数 据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数 据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法， 该数据结构就是索引。