一、B樹引入

二叉搜索樹、平衡二叉樹、紅黑樹都是動態(tài)查找樹，典型的二叉搜索樹結構，查找的時間復雜度和樹的高度相關O(log2N)。

1）數據雜亂無章-------線性查找--O（n）

2）數據有序-------二分查找 ---O(log 2 n） ?最差退化成單支樹-----線性結構

3）二叉搜索樹、AVL樹、紅黑樹 --------O(log2 n)

數據一般保存在磁盤上，若數據量過大不能全部加載到內存，為了訪問所有數據，使用如下搜索樹結構保存數據：樹的結點中保存權值和磁盤的地址

那如何加速對數據的訪問速度呢？

提高I/O的時間

降低樹的高度--平衡多叉樹

二、B樹定義

1970年，R.Bayer和E.mccreight提出了一種適合外查找的樹，它是一種平衡的多叉樹，稱為B樹。
（有些地方寫的是B-樹，注意不要誤讀成"B減樹"）
一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質：
1. 根節(jié)點至少有兩個孩子
2. 每個非根節(jié)點至少有M/2(上取整)個孩子,至多有M個孩子
3. 每個非根節(jié)點至少有M/2-1(上取整)個關鍵字,至多有M-1個關鍵字，并且以升序排列

4. key[i]和key[i+1]之間的孩子節(jié)點的值介于key[i]、key[i+1]之間

一次插入的過程：53, 75, 139, 49, 145, 36, 101

#pragma once #include <iostream> #include <stdlib.h>using namespace std;template<class K, int M> struct BTreeNode {typedef BTreeNode<K, M> Node;K _keys[M];//多給一個位置是為了先插入方便分裂Node* _sub[M+1];Node* _parent;size_t _size;//記錄關鍵字的個數BTreeNode():_parent(NULL),_size(0){for(size_t i = 0; i < M; i++){_keys[i] = K();_sub[i] = 0;}_sub[M] = 0;} };template<class K, int M> class BTree {typedef BTreeNode<K, M> Node; public:BTree():_pRoot(NULL){}void Inorder(){_Inorder(_pRoot);}~BTree(){_Destroy(_pRoot);}bool Insert(const K& key){if(NULL == _pRoot){_pRoot = new Node();_pRoot->_keys[0] = key;_pRoot->_size++;return true;}pair<Node*, size_t> temp = _Find(key);if(temp.second != -1){return false;}Node* cur = temp.first;Node* sub = NULL;K newKey = key;while(1){_InsertKey(cur, newKey, sub);if(cur->_size < M){return true;}while(cur->_size >= M){size_t mid = cur->_size / 2;Node* NewNode = new Node;for(size_t i = mid+1; i < cur->_size; i++){int j = 0; //新節(jié)點的下標NewNode->_keys[j] = cur->_keys[i];NewNode->_size++;cur->_keys[i] = K();//復制之后，對應的原位置key置為初始值。j++;}int j = 0;for(size_t i = mid+1; i < cur->_size+1; i++){NewNode->_sub[j] = cur->_sub[i];if(NewNode->_sub[j])NewNode->_sub[j]->_parent = NewNode;j++;cur->_sub[i] = NULL;}if(cur == _pRoot){Node* temp = new Node();temp->_keys[0] = cur->_keys[mid];cur->_keys[mid] = K();cur->_size = mid;temp->_size++;temp->_sub[0] = cur;cur->_parent = temp;temp->_sub[1] = NewNode;NewNode->_parent = temp;_pRoot = temp;return true;}newKey = cur->_keys[mid];cur->_keys[mid] = K();cur->_size = mid;sub = NewNode;}cur = cur->_parent;}}protected:pair<Node*, size_t> _Find(const K& key){Node* cur = _pRoot;Node* parent = NULL;while(cur){size_t i = 0;while(i < cur->_size){if(cur->_keys[i] < key)i++;else if(cur->_keys[i] > key)break;elsereturn pair<Node*, size_t>(cur, i);}parent = cur;cur = cur->_sub[i];}return pair<Node*, size_t>(parent, -1);}void _InsertKey(Node* cur,const K& Key,Node* sub){int i = cur->_size-1;while(i >= 0){if(cur->_keys[i] > Key){//移動關鍵字位置cur->_keys[i+1] = cur->_keys[i];//移動子樹的位置cur->_sub[i+2] = cur->_sub[i+1];i--;}elsebreak;}cur->_keys[i+1] = Key;cur->_sub[i+2] = sub;if(sub)sub->_parent = cur;cur->_size++;}void _Inorder(Node* _pRoot){if(NULL == _pRoot)return;size_t i = 0;for(; i < _pRoot->_size; i++){_Inorder(_pRoot->_sub[i]);cout<<_pRoot->_keys[i]<<" ";}_Inorder(_pRoot->_sub[i]);}void _Destroy(Node* _pRoot){if(NULL == _pRoot)return;size_t i = 0;for(; i < _pRoot->_size; i++){_Destroy(_pRoot->_sub[i]);delete _pRoot->_sub[i];}_Destroy(_pRoot->_sub[i]);delete _pRoot->_sub[i];}private:Node* _pRoot; };void test() {BTree<int, 3> bt;int array[] = {53, 75, 139, 49, 145, 36, 101};for(int i = 0; i < sizeof(array)/sizeof(array[0]); i++){bt.Insert(array[i]);}bt.Inorder(); }

總結

以上是生活随笔為你收集整理的数据结构：神奇的B树实现解析（有图有代码有真相！！！）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。