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；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。