b樹演算法
① 為什麼說基於b樹索引的nested loop演算法更適合返回少量結果的連接操作
誰跟你說B樹是2叉樹了？ 1. 首先 B樹不是二叉樹， 可以有很多叉， 取決於定義Key的數量， 或者是權的數量 2. B樹是平衡樹的種類之一， 比二叉樹的優點是， 由於它始終調整為「平衡」， 那麼搜索時，始終能保持LOGN的效率
② 為什麼資料庫採用B樹，搜索引擎用Hash
關系型資料庫的索引大多採用B/B+樹來作為存儲結構，而全文檢索的搜索引擎則主要採用Hash來作為索引的存儲結構，這兩類系統的演算法都比較成熟了，為什麼它們要在各自的應用環境下採用這兩種數據結構來存儲索引。
我個人的理解是：
資料庫系統庫表比較多，講究的是靈活，尤其是在空間上的flexible很重要，而B/B+樹在擴展上具有較好的空間優勢（當表中數據行比較少的時候，其索引也比較小，比較靈活且節省空間），當然其查詢速度在在O(logN)級別上也算是比較高了。
而搜索引擎對查詢速度要求很高，所以Hash是查詢速度最快的一種索引數據結構，但是它是犧牲了空間的代價，因為動態Hash一直是一個比較難的問題，所以開始為了保證較合適的填充因子，所以不得不開一個比較大的空間來存儲索引，此時數據內容的條數可能並不是很多。
③ 已知3階B樹如題所示，畫出將關鍵字47和66依次插入後的B樹
首先，這是由B樹的插入演算法本身所決定的，B樹的插入演算法規定，當插入一個關鍵字至某一個節點而引起該節點因關鍵字過多而必須分裂時，應當把該節點中「處於中位」的關鍵字提升到父節點中去，這樣，其他節點得以平衡地一分為二。
其次，之所以有這樣的規定，並不是隨意為之的，以你的這個題為例（假定節點之內採用順序比較法），假若按你的想法把74提升上去，那麼從根節點60開始，查找74需比較2次，查找66需比較3次，查找68需比較4次（因為66與68同處一個節點內，查到68之前還得經過66），平均比較（2+3+4）/3=3次
然而若把68提上去，那麼查68需比較2次，查66和74都只需比較3次（66和74分布在68的兩側），平均（2+3+3）/3=8/3次
這還只是節點比較少的情況，節點多的話效率的差異會更加明顯。
記住計算機科學中一個關鍵的准則：「2是一個至關重要的數字」，設計各種演算法時，盡量追求二分和平衡，保持平衡，這是很多高效演算法的核心所在。
有問題請追問。
④ 數據結構B樹的設計與實現
B樹的插入演算法在編寫過程中還是覺得比較難寫的，主要的問題是，結點的分裂，
對葉子結點的分裂和對非葉節點的分裂不一樣，還有就是當ptr->parent==NULL,
需要新建父結點，而新建的結點始終是樹的根結點，還有結點分裂過程中子樹指
針的變化還是很復雜的，不過終於實現了，分享一下我的代碼，可以直接運行，
本程序沒有包含我編寫的其他頭文件，代碼如下，大家多多討論：
另外，由於B樹不同於其他的樹，所有我考慮了一下，還是採用縮進格式來顯示
B樹了，因為每個結點有多個關鍵碼，所以用廣義表形式不顯示不好。
#ifndef BTREE_H
#define BTREE_H
#include<iostream.h>
#include<stdlib.h>
const int maxValue=10000;
/////////////////////////////////////////////////
//BTreeNode<T>B樹的結點的定義
/////////////////////////////////////////////////
template<class T>
struct BTreeNode
{
int n; //結點中關鍵碼的個數
BTreeNode<T>* parent; //當前結點的父結點的指針
T* key; //m+1個元素存放關鍵碼,其中key[0]和key[m]沒有用
BTreeNode<T>** //子樹指針的結點數組(一共有m棵子樹),m+1個元素
subTree; //最後一個元素subTree[m]在插入溢出的時候使用
int** recptr; //每個索引項中指向數據區相應記錄起始地址的指針數組
BTreeNode(int m) //構造函數
{
n=0; //關鍵碼個數初始化為0
parent=NULL; //父結點指針初始化為空
key=new T[m+1]; //開辟關鍵碼數組的空間
subTree=new //開辟子樹的指針數組的內存空間
BTreeNode<T>*[m+1]; //從p0,p1,p2,...p(m-1)共m棵子樹
for(int i=0;i<=m;i++)
subTree[i]=NULL; //子樹數組先全部初始化為空
};
bool Insert(const T& x //把一個關鍵碼插入到當前的B樹結點中
,BTreeNode<T>* p) //也把附帶的新建的右子樹的指針插入subTree[]中
{
for(int i=1;i<=n;i++) //尋找插入關鍵碼的位置
{
if(x<key[i])
break;
};
for(int j=n;j>=i;j--) //挪處新的插入位置來
key[j+1]=key[j];
key[i]=x; //插入結點
n++;
for(j=n;j>=i;j--) //把新分裂開來的右子樹結點插入subTree[]中
subTree[j+1]=subTree[j];
subTree[i]=p;
return true;
};
void Display() //顯示當前結點所有關鍵碼
{
for(int i=1;i<=n;i++)
cout<<key[i]<<" ";
};
};
/////////////////////////////////BTree<T>定義結束
/////////////////////////////////////////////////
//Triple<T>結構 返回搜索結果用的三元組
/////////////////////////////////////////////////
template<class T>
struct Triple
{
BTreeNode<T>* r; //結點指針
int i; //關鍵碼在當前結點中的序號
int tag; //tag=0:搜索成功,tag=1:搜索失敗
};
////////////////////////////////Triple<T>結構結束
/////////////////////////////////////////////////
//BTree<T> B樹的定義;
//m階B樹的根至少有兩個子樹，
//其他的結點至少應該有int(m/2)+1個子樹
//所有的失敗結點都在一個層次上
/////////////////////////////////////////////////
template<class T>
class BTree
{
private:
BTreeNode<T>* root; //樹根結點指針
int m; //即B樹的階數
public:
BTree(int x) //空構造函數,構造一棵空x路的搜索樹
{root=NULL;m=x;};
BTree(int x,BTreeNode<T>* r)
{root=r;m=x;}; //用指定的樹根來初始化當前的m路搜索樹
void Insert( //在樹指定父結點的情況下插入一個結點
BTreeNode<T>* pa, //指定要出入的位置的父結點
BTreeNode<T>* subTree, //要插入的結點的指針
int i); //表示插入到pa的第i個子樹的位置
Triple<T> //搜索指定關鍵碼x對應的結點
Search(const T& x);
void RootFirst( //遞歸:以先根的方式遍歷當前的搜索樹
BTreeNode<T>* subTree);
void RootFirst() //調用上面的遞歸函數
{RootFirst(root);};
bool Insert(const T& x); //B樹的插入操作
void Display(
BTreeNode<T>* p,int i); //遞歸:以縮進的格式顯示當前的B樹
void Display() //調用上面的遞歸函數
{cout<<"*****當前B樹的縮進結構顯示*****:"<<endl;
Display(root,1);};
};
//////////////////////////////////////B樹聲明結束
/////////////////////////////////////////////////
//RootFirst()公有成員函數
//以先根的方式遞歸遍歷當前B樹
/////////////////////////////////////////////////
template<class T>
void BTree<T>::RootFirst(BTreeNode<T>* st)
{
if(st!=NULL)
{
int n=st->n;
cout<<"當前結點有"<<n
<<"個關鍵碼:"<<endl;
for(int k=1;k<=n;k++) //輸出當前結點的所有的關鍵碼
cout<<st->key[k]<<" ";
cout<<endl<<endl;
for(int i=0;i<=n;i++) //遞歸輸出所有的子樹
RootFirst(st->subTree[i]);
};
};
//////////////////////////////RootFirst()函數結束
/////////////////////////////////////////////////
//Search()公有成員函數 搜索具有指定關鍵碼的
//的結點並且以三元組的形式進行返回,如果沒有搜索
//成功就把該關鍵碼插入到當前駐留的結點中去
/////////////////////////////////////////////////
template<class T>
Triple<T> BTree<T>::Search(const T& x)
{
Triple<T> result; //結果三元組
BTreeNode<T>* ptr=root; //從根結點開始搜索
BTreeNode<T>* pre;
/*從根結點開始往下查找*/
int i;
while(ptr!=NULL)
{
for(i=1;i<=ptr->n;i++) //在結點內部進行順序搜索
{
if(ptr->key[i]==x) //如果找到
{
result.r=ptr; //當前查找駐留的結點指針
result.i=i; //查找成功的關鍵碼
result.tag=1; //是否查找成功
return result;
};
if(ptr->key[i]>x) //查找失敗
break;
};
pre=ptr;
ptr=ptr->subTree[i-1]; //從失配的關鍵碼左邊的子樹繼續查找
};
/*如果查找失敗*/
result.r=pre;
result.i=i; //可以在i-1和i之間進行插入
result.tag=0; //查找失敗
return result;
};
/////////////////////////////////Search()函數結束
/////////////////////////////////////////////////
//Insert()公有成員函數 B樹的插入操作
//把指定的關鍵碼插入到B樹中,使得仍然滿足B樹的要求
//首先對B樹進行搜索,如果關鍵碼已經存在則插入失敗,
//否則執行插入，並按B樹要求進行調整
//一般來說,執行插入的肯定是在葉子結點上進行
//但是如果查找成功的話,可能在非葉子結點上就結束了
/////////////////////////////////////////////////
template<class T>
bool BTree<T>::Insert(const T& x)
{
/*如果當前的B樹是空的,就新建之*/
if(root==NULL) //如果當前的B樹是空的
{
root=new BTreeNode<T>(m); //新建一個結點
root->Insert(x,NULL); //把關鍵碼插入到key[]數組第一個位置
return true;
};
/*如果當前的B樹不空,就搜索該樹*/
Triple<T> Tp; //查找結果三元組
Tp=Search(x);
int IsIn=Tp.tag;
if(IsIn==1) //關鍵碼已經存在
{
cout<<"關鍵碼已存在!"<<endl;
return false; //插入失敗
};
/*插入關鍵碼直到結點關鍵碼不溢出為止*/
BTreeNode<T>* ptr=Tp.r; //查找失敗而駐留的結點
int loc=Tp.i-1; //在k[loc]後進行插入
int pkey=x;
BTreeNode<T>* p=NULL; //隨關鍵一起要插入的右子樹的根結點
do
{
ptr->Insert(pkey,p); //把關鍵碼和相關的新分裂的右結點插入當前結點
if(ptr->n>m-1) //如果關鍵碼溢出,則需要進行調整
{
/*以下處理結點的分裂*/
int k=ptr->key[m/2+1]; //提取出要上提的關鍵碼
BTreeNode<T>* right //建立分裂後右邊的結點
=new BTreeNode<T>(m);
right->n=ptr->n-m/2-1; //右結點的關鍵碼個數
for(int i=m/2+2;i<=ptr->n;i++)
right->key[i-m/2-1] //把右半邊的關鍵碼復制進入右結點
=ptr->key[i];
for(i=m/2+1;i<=ptr->n;i++)
{
right->subTree[i-m/2-1]
=ptr->subTree[i]; //把相應的分裂後的右結點子樹指針復制入新結點
}
ptr->n=m/2; //修改原結點使之成為左結點
right->parent
=ptr->parent; //新分裂的結點
p=right; //p是隨k一起上提的新建分裂右結點指針
pkey=k;
/*如果當前的結點沒有父結點*/
if(ptr->parent==NULL) //如果當前結點沒有父結點,就新建父結點
{
BTreeNode<T>* newp //新建一個父結點
=new BTreeNode<T>(m);
newp->key[1]=k; //插入新關鍵碼
newp->subTree[0] //新關鍵碼左邊的子樹
=ptr;
newp->subTree[1] //新關鍵碼右邊的子樹
=right;
newp->n=1; //新關鍵碼個數為1
ptr->parent=newp; //設置父結點指針
right->parent=newp;
root=newp;
return true; //插入成功並結束
}
else //如果有父結點存在
ptr=ptr->parent; //把上提的關鍵碼繼續插入父結點
}
else //不溢出則插入成功
return true;
}while(ptr!=NULL);
return true;
};
/////////////////////////Insert()公有成員函數結束
/////////////////////////////////////////////////
//Display()公有成員函數
//遞歸:顯示當前B樹的縮進格式
/////////////////////////////////////////////////
template<class T>
void BTree<T>::Display(BTreeNode<T>* p,int i)
{
if(p!=NULL)
{
for(int j=0;j<i;j++)
cout<<" "; //控制縮進的格數
cout<<"當前結點是:關鍵碼個數"<<p->n<<" "
<<"關鍵碼的內容是";
for(int k=1;k<=p->n;k++)//顯示當前結點所有關鍵碼
cout<<p->key[k]<<" ";
cout<<endl;
for(k=0;k<=p->n;k++) //遞歸顯示子樹,遞歸向後縮進
Display(p->subTree[k],i+5);
};
};
////////////////////////////////Display()函數結束
#endif
#include"BTree.h"
/////////////////////////////////////////////////
//main()函數 測試B樹的程序
/////////////////////////////////////////////////
int main()
{
BTree<int> BT(3);
BT.Insert(53); //依此在B樹中插入關鍵碼
BT.Insert(75);
BT.Insert(139);
BT.Insert(49);
BT.Insert(145);
BT.Insert(36);
BT.Insert(101);
BT.Insert(150);
BT.Insert(170);
BT.Insert(25);
BT.Insert(13);
BT.Display(); //顯示當前B樹的內容
return 0;
};
///////////////////////////////////main()函數結束
⑤ B樹的示例
當在葉子結點處於第L+1層的B樹中插入關鍵字時，被插入的關鍵字總是進入第L層的結點。
若在一個包含j<m-1個關鍵字的結點中插入一個新的關鍵字，則把新的關鍵字直接插入該結點即可；但若把一個新的關鍵字插入到包含m-1（m為B-樹的階）個關鍵字的結點中，則將引起結點的分裂。在這種情況下，要把這個結點分裂為兩個，並把中間的一個關鍵字（中間的關鍵字滿足：左邊的小於該關鍵字；右邊的大於該關鍵字；故正好可以作為雙親）拿出來插到該結點的雙親結點中去，雙親結點也可能是滿的，就需要再分裂、再往上插，從而可能導致B-樹可能朝著根的方向生長。
插入演算法演示：插入之前如圖1：
插入之後如圖2：
4. B-樹的刪除:
當從B-樹中刪除一個關鍵字Ki時，總的分為以下兩種情況：
如果該關鍵字所在的結點不是最下層的非葉子結點，則先需要把此關鍵字與它在B-樹中後繼對換位置，即以指針Pi所指子樹中的最小關鍵字Y代替Ki，然後在相應的結點中刪除Y。
如果該關鍵字所在的結點正好是最下層的非葉子結點，這種情況下，會有以下兩種可能：
① 若該關鍵字Ki所在結點中的關鍵字個數不小於┌m/2┐，則可以直接從該結點中刪除該關鍵字和相應指針即可。
② 若該關鍵字Ki所在結點中的關鍵字個數小於┌m/2┐，則直接從結點中刪除關鍵字會導致此結點中所含關鍵字個數小於┌m/2┐-1 。這種情況下，需考察該結點在B樹中的左或右兄弟結點，從兄弟結點中移若干個關鍵字到該結點中來（這也涉及它們的雙親結點中的一個關鍵字要作相應變化），使兩個結點中所含關鍵字個數基本相同；但如果其兄弟結點的關鍵字個數也很少，剛好等於┌m/2┐-1 ，這種移動則不能進行，這種情形下，需要把刪除了關鍵字Ki的結點、它的兄弟結點及它們雙親結點中的一個關鍵字合並為一個結點。
⑥ HASH與B樹的聯系與區別
沒啥聯系。
b樹，一種結構，用以存放數據等等。
hash，演算法，包括很多種具體的演算法（數學邏輯），
db根據hash算出來的值控制數據存放的結構。
⑦ B樹演算法難么
感覺挺難。
B樹的定義
假設B樹的度為t（t>=2），則B樹滿足如下要求：（參考演算法導論）
（1）
每個非根節點至少包含t-1個關鍵字，t個指向子節點的指針；至多包含2t-1個關鍵字，2t個指向子女的指針（葉子節點的子女為空）。
（2）
節點的所有key按非降序存放，假設節點的關鍵字分別為K[1],
K[2]
…
K[n],
指向子女的指針分別為P[1],
P[2]…P[n+1]，其中n為節點關鍵字的個數。則有：
P[1]
<=
K[1]
<=
P[2]
<=
K[2]
…..<=
K[n]
<=P[n+1]
//
這里P[n]也指其指向的關鍵字
（3）
若根節點非空，則根節點至少包含兩個子女；
（4）
所有的葉子節點都在同一層。
B樹的搜索，search（root,
target）
從root出發，對每個節點，找到大於或等於target關鍵字中最小的K[i]，如果K[i]與target相等，則查找成功；否則在P[i]中遞歸搜索target，直到到達葉子節點，如仍未找到則說明關鍵字不在B樹中，查找失敗。
B樹的插入，insert(root,target)
B樹的插入需要沿著搜索的路徑從root一直到葉節點，根據B樹的規則，每個節點的關鍵字個數在[t-1,
2t-1]之間，故當target要加入到某個葉子時，如果該葉子節點已經有2t-1個關鍵字，則再加入target就違反了B樹的定義，這時就需要對該葉子節點進行分裂，將葉子以中間節點為界，分成兩個包含t-1個關鍵字的子節點，同時把中間節點提升到該葉子的父節點中，如果這樣使得父節點的關鍵字個數超過2t-1，則要繼續向上分裂，直到根節點，根節點的分裂會使得樹加高一層。
上面的過程需要回溯，那麼能否從根下降到葉節點後不回溯就能完成節點的插入呢？答案是肯定的，核心思想就是未雨綢繆，在下降的過程中，一旦遇到已滿的節點（關鍵字個數為2t-1），就就對該節點進行分裂，這樣就保證在葉子節點需要分裂時，其父節點一定是非滿的，從而不需要再向上回溯。
B樹的刪除，delete(root,target)
在刪除B樹節點時，為了避免回溯，當遇到需要合並的節點時就立即執行合並，B樹的刪除演算法如下：從root向葉子節點按照search規律遍歷：
（1）
如果target在葉節點x中，則直接從x中刪除target，情況（2）和（3）會保證當再葉子節點找到target時，肯定能借節點或合並成功而不會引起父節點的關鍵字個數少於t-1。
（2）
如果target在分支節點x中：
（a）
如果x的左分支節點y至少包含t個關鍵字，則找出y的最右的關鍵字prev，並替換target，並在y中遞歸刪除prev。
（b）
如果x的右分支節點z至少包含t個關鍵字，則找出z的最左的關鍵字next，並替換target，並在z中遞歸刪除next。
（c）
否則，如果y和z都只有t-1個關鍵字，則將targe與z合並到y中，使得y有2t-1個關鍵字，再從y中遞歸刪除target。
（3）
如果關鍵字不在分支節點x中，則必然在x的某個分支節點p[i]中，如果p[i]節點只有t-1個關鍵字。
（a）
如果p[i-1]擁有至少t個關鍵字，則將x的某個關鍵字降至p[i]中，將p[i-1]的最大節點上升至x中。
（b）
如果p[i+1]擁有至少t個關鍵字，則將x個某個關鍵字降至p[i]中，將p[i+1]的最小關鍵字上升至x個。
（c）
如果p[i-1]與p[i+1]都擁有t-1個關鍵字，則將p[i]與其中一個兄弟合並，將x的一個關鍵字降至合並的節點中，成為中間關鍵字。
⑧ 數據結構B樹的生成問題
不唯一吧，會根據你的演算法（即是按照BST還是AVL還是Huffman還是其他演算法）來構造。除非權值一樣，才會生成唯一的B樹。
⑨ b+樹和b樹的區別是什麼
B+樹索引是B+樹在資料庫中的一種實現，是最常見也是資料庫中使用最為頻繁的一種索引。B+樹中的B代表平衡（balance），而不是二叉（binary）。
（1）非葉子節點只能允許最多兩個子節點存在。
（2）每一個非葉子節點數據分布規則為左邊的子節點小當前節點的值，右邊的子節點大於當前節點的值(這里值是基於自己的演算法規則而定的，比如hash值)。
(9)b樹演算法擴展閱讀：
與普通樹不同，普通樹的節點個數至少為1，而二叉樹的節點個數可以為0；普通樹節點的最大分支度沒有限制。
而二叉樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二叉樹的節點有左、右次序之分。