数据结构——B-树
1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树 (后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一 棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：
目录
一.常见的搜索结构
以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的 地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据
使用平衡二叉树搜索树的缺陷：
平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时， 访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以接受的结果
使用哈希表的缺陷:
哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的
那如何加速对数据的访问呢？
- 提高IO的速度(SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
- 降低树的高度---多叉树平衡树
二.B-树概念
1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树 (后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：
- 根节点至少有两个孩子
- 每个分支节点都包含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-树的插入分析及实现
1.插入分析
为了简单起见，假设M = 3. 即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点应该有三个孩子，为了后续实现简单期间，节点的结构如下
注意：孩子永远比数据多一个
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：
pair<Node*, int> Find(const K& 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);
}
插入总结:
- 如果树为空，直接插入新节点中，该节点为树的根节点
- 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
- 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
- 按照插入排序的思想将该元素插入到找到的节点中
- 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
- 如果插入后节点不满足B树的性质，需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4
- 如果向上已经分裂到根节点的位置，插入结束
2.插入实现
1. B-树的节点设计
template<class K,size_t M>
struct BTreeNode
{
//为了方便插入后分裂,多开一个空间
K _keys[M];
BTreeNode<K, M>* _subs[M + 1];
BTreeNode<K, M>* _parent;
size_t _n;//记录实际存储多少个关键字
BTreeNode()
{
for (size_t i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};2.插入key的过程
void InsertKey(Node* node, const K& key, Node* child)
{
int end = node->_n - 1;
while (end >= 0)
{
if (key < node->_keys[end])
{
node->_keys[end + 1] = node->_keys[end];
node->_subs[end + 2] = node->_subs[end + 1];
--end;
}
else
{
break;
}
}
node->_keys[end + 1] = key;
node->_subs[end + 2] = child;
if (child)
{
child->_parent = node;
}
node->_n++;
}3.B-树的插入实现
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node;
_root->_keys[0] = key;
_root->_n++;
return true;
}
pair<Node*, int> ret = Find(key);
if (ret.second >= 0)
{
return false;
}
Node* parent = ret.first;
K newkey = key;
Node* child = nullptr;
while (1)
{
InsertKey(parent, newkey, child);
//满了就分裂,没有满插入结束
if (parent->_n < M)
{
return true;
}
else
{
size_t mid = M / 2;
//分裂一半[mid + 1, M - 1]给兄弟
Node* brother = new Node;
size_t j = 0;
size_t i = mid + 1;
for( ; i <= M - 1; ++i)
{
brother->_keys[j] = parent->_keys[i];
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
++j;
parent->_keys[i] = K();
parent->_subs[i] = nullptr;
}
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
parent->_subs[i] = nullptr;
brother->_n = j;
parent->_n -= (brother->_n + 1);
K midkey = parent->_keys[mid];
parent->_keys[mid] = K();
if (parent->_parent == nullptr)
{
_root = new Node;
_root->_keys[0] = midkey;
_root->_subs[0] = parent;
_root->_subs[1] = brother;
_root->_n = 1;
parent->_parent = _root;
brother->_parent = _root;
break;
}
else
{
newkey = midkey;
child = brother;
parent = parent->_parent;
}
}
}
return true;
}4.B-树的验证
对B树进行中序遍历，如果能得到一个有序的序列，说明插入正确
//左根 左根 ......右
void _InOrder(Node* root)
{
if (root == nullptr)
return;
size_t i = 0;
for (; i < root->_n; ++i)
{
_InOrder(root->_subs[i]);//左子树
cout << root->_keys[i] << " ";//根
}
_InOrder(root->_subs[i]);//最后的右子树
}
void InOrder()
{
_InOrder(_root);
}
5.B-树的性能分析
对于一棵节点为N度为M的B-树，查找和插入需要 和
次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要
和
之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素
B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则 ，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数
四.B+树和B*树
1.B+树
B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：
- 分支节点的子树指针与关键字个数相同
- 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
- 所有叶子节点增加一个链接指针链接在一起
- 所有关键字及其映射数据都在叶子节点出现
B+树的特性:
- 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的
- 不可能在分支节点中命中
- 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层
2.B*树
B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针
B+树的分裂:
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针
B*树的分裂:
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针
所以，B*树分配新结点的概率比B+树要低，空间使用率更高
3.总结
通过以上介绍，大致将B树，B+树，B*树总结如下：
- B树：有序数组+平衡多叉树
- B+树：有序数组链表+平衡多叉树
- B*树：一棵更丰满的，空间利用率更高的B+树
五.B-树的应用
1.索引
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如： 书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构
MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说： 索引就是数据结构
当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法， 该数据结构就是索引
2.MySQL索引简介
mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎，如下：
MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的
注意：索引是基于表的，而不是基于数据库的
1.MyISAM
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：
上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索 引要求key是唯一的，而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引，则此索引 的结构如下图所示：
同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”
2.InnoDB
InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版 本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但 InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同
第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的， 索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此 InnoDB表数据文件本身就是主索引
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录， 这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数 据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主 键，这个字段长度为6个字节，类型为长整型
第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录
六.整体代码
1.BTree.h
#pragma once
template<class K,size_t M>
struct BTreeNode
{
//为了方便插入后分裂,多开一个空间
K _keys[M];
BTreeNode<K, M>* _subs[M + 1];
BTreeNode<K, M>* _parent;
size_t _n;//记录实际存储多少个关键字
BTreeNode()
{
for (size_t i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};
template<class K,size_t M>
class BTree
{
typedef BTreeNode<K, M> Node;
public:
pair<Node*, int> Find(const K& 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);
}
void InsertKey(Node* node, const K& key, Node* child)
{
int end = node->_n - 1;
while (end >= 0)
{
if (key < node->_keys[end])
{
node->_keys[end + 1] = node->_keys[end];
node->_subs[end + 2] = node->_subs[end + 1];
--end;
}
else
{
break;
}
}
node->_keys[end + 1] = key;
node->_subs[end + 2] = child;
if (child)
{
child->_parent = node;
}
node->_n++;
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node;
_root->_keys[0] = key;
_root->_n++;
return true;
}
pair<Node*, int> ret = Find(key);
if (ret.second >= 0)
{
return false;
}
Node* parent = ret.first;
K newkey = key;
Node* child = nullptr;
while (1)
{
InsertKey(parent, newkey, child);
//满了就分裂,没有满插入结束
if (parent->_n < M)
{
return true;
}
else
{
size_t mid = M / 2;
//分裂一半[mid + 1, M - 1]给兄弟
Node* brother = new Node;
size_t j = 0;
size_t i = mid + 1;
for( ; i <= M - 1; ++i)
{
brother->_keys[j] = parent->_keys[i];
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
++j;
parent->_keys[i] = K();
parent->_subs[i] = nullptr;
}
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
parent->_subs[i] = nullptr;
brother->_n = j;
parent->_n -= (brother->_n + 1);
K midkey = parent->_keys[mid];
parent->_keys[mid] = K();
if (parent->_parent == nullptr)
{
_root = new Node;
_root->_keys[0] = midkey;
_root->_subs[0] = parent;
_root->_subs[1] = brother;
_root->_n = 1;
parent->_parent = _root;
brother->_parent = _root;
break;
}
else
{
newkey = midkey;
child = brother;
parent = parent->_parent;
}
}
}
return true;
}
//左根 左根 ......右
void _InOrder(Node* root)
{
if (root == nullptr)
return;
size_t i = 0;
for (; i < root->_n; ++i)
{
_InOrder(root->_subs[i]);//左子树
cout << root->_keys[i] << " ";//根
}
_InOrder(root->_subs[i]);//最后的右子树
}
void InOrder()
{
_InOrder(_root);
}
private:
Node* _root = nullptr;
};
void TestBTree()
{
int a[] = { 53,139,75,49,145,36,101 };
BTree<int, 3> t;
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
}2.test.cpp
#include<iostream>
using namespace std;
#include"BTree.h"
int main()
{
TestBTree();
}
助力广东及东莞地区开发者，代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展，成为松山湖开发者首选的工作与学习平台
更多推荐
108
0- 0
已为社区贡献1条内容
所有评论(0)