一種適合外查找的樹，它是一種平衡的多叉樹，稱為B樹。
站在用戶的角度思考問題，與客戶深入溝通，找到梁園網(wǎng)站設(shè)計(jì)與梁園網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、空間域名、虛擬主機(jī)、企業(yè)郵箱。業(yè)務(wù)覆蓋梁園地區(qū)。
一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質(zhì)：
根節(jié)點(diǎn)至少有兩個(gè)孩子
每個(gè)非根節(jié)點(diǎn)有[M/2
,M]個(gè)孩子
每個(gè)非根節(jié)點(diǎn)有[M/2-1,M-1]個(gè)關(guān)鍵字，并且以升序排列
key[i]和key[i+1]之間的孩子節(jié)點(diǎn)的值介于key[i]、key[i+1]之間
所有的葉子節(jié)點(diǎn)都在同一層
注：使用B-tree結(jié)構(gòu)可以顯著減少定位記錄時(shí)所經(jīng)歷的中間過程，從而加快存取速度。按照翻譯，B 通常認(rèn)為是Balance的簡稱。這個(gè)數(shù)據(jù)結(jié)構(gòu)一般用于數(shù)據(jù)庫的索引，綜合效率較高。
B-tree有以下特性：
1、關(guān)鍵字集合分布在整棵樹中；
2、任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；
3、搜索有可能在非葉子節(jié)點(diǎn)結(jié)束；
4、其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找；
5、自動(dòng)層次控制；
鑒于B-tree具有良好的定位特性，其常被用于對(duì)檢索時(shí)間要求苛刻的場(chǎng)合，例如：
1、B-tree索引是數(shù)據(jù)庫中存取和查找文件(稱為記錄或鍵值)的一種方法。
2、硬盤中的結(jié)點(diǎn)也是B-tree結(jié)構(gòu)的。與內(nèi)存相比，硬盤必須花成倍的時(shí)間來存取一個(gè)數(shù)據(jù)元素，這是因?yàn)橛脖P的機(jī)械部件讀寫數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)趕不上純電子媒體的內(nèi)存。與一個(gè)結(jié)點(diǎn)兩個(gè)分支的二元樹相比，B-tree利用多個(gè)分支（稱為子樹）的結(jié)點(diǎn)，減少獲取記錄時(shí)所經(jīng)歷的結(jié)點(diǎn)數(shù)，從而達(dá)到節(jié)省存取時(shí)間的目的。
#pragma once
#include
using namespace std;
template
struct BTreeNode
{
K _keys[M];
BTreeNode* _subs[M + 1];
BTreeNode* _parent;
size_t _size;
BTreeNode()
:_parent(NULL)
, _size(0)
{
for (int i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = NULL;
}
_subs[M] = NULL;
}
};//K
template
struct BTreeNodeKV
{
pair _kvs[M];
BTreeNodeKV* _subs[M + 1];
BTreeNodeKV* _parent;
size_t _size;
};
template
class BTree
{
typedef BTreeNode Node;
public:
BTree()
:_root(NULL)
{}
pair Find(K& key)
{
if (_root == NULL)
return pair(NULL, -1);
Node* cur=_root;
Node* parent = NULL;
while (cur)
{
int size = cur->_size;
int i;
for (i = 0; i < size;)
{
if (cur->_keys[i] == key)
return pair(cur, i);
else if (cur->_keys[i] < key)
{
++i;
}
else
break;
}
parent = cur;
cur = cur->_subs[i];
}
return pair(parent, -1);
}
void _Insert(Node* cur,K& key, Node* sub)
{
int end = cur->_size - 1;
while (end >= 0)
{
if (cur->_keys[end] > key)
{
cur->_keys[end + 1] = cur->_keys[end];
cur->_subs[end + 2] = cur->_subs[end+1];
--end;
}
else
break;
}
cur->_keys[end + 1] = key;
cur->_subs[end + 2] = sub;
++cur->_size;
if (sub)
sub->_parent=cur;
}
bool Insert(K& key)
{
if (_root == NULL)
{
_root = new Node;
_root->_keys[0] = key;
_root->_size = 1;
return true;
}
else
{
pair ret = Find(key);
if (ret.second != -1)
return false;
else
{
Node* cur = ret.first;
K newkey = key;
Node* insert_sub = NULL;//第一次插入時(shí)insert_sub為NULL
while (1)
{
_Insert(cur, newkey, insert_sub);
if (cur->_size_keys[index] = cur->_keys[i];
cur->_keys[i] = K();//還原為K類型的默認(rèn)值
sub->_subs[index] = cur->_subs[i];
cur->_subs[i] = NULL;
++index;
++i;
++sub->_size;
}
sub->_subs[index] = cur->_subs[i];
cur->_subs[i - 1] = NULL;
cur->_size -= (index+1);//減去右邊和key的大小
if (cur->_parent == NULL)
{
_root = new Node;
_root->_keys[0] = cur->_keys[div];
cur->_keys[div] = K();
_root->_subs[0] = cur;
cur->_parent = _root;
_root->_subs[1] = sub;
sub->_parent=_root;
_root->_size = 1;
return true;
}
else
{
insert_sub = sub;
newkey = cur->_keys[div];
cur = cur->_parent;
}
}
return true;
}
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
protected:
void _InOrder(Node* root)
{
if (root == NULL)
return;
int i = 0;
for (i = 0; i < root->_size; ++i)
{
_InOrder(root->_subs[i]);
cout << root->_keys[i] << " ";
}
_InOrder(root->_subs[i]);
}
protected:
Node* _root;
};
void Test1()
{
//int arr[] = { 20, 30, 10 };
/*BTree b;
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
b.Insert(arr[i]);
}*/
int arr[] = { 53, 75, 139, 49, 145, 36, 101 };
BTree b;
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
{
b.Insert(arr[i]);
}
b.InOrder();
}
#include"BTree.h"
int main()
{
Test1();
system("pause");
return 0;
}
文章標(biāo)題：BTree---------詳談
文章源于：
http://weahome.cn/article/ijgijc.html
重慶分公司
重慶分公司
