B树底层实现模板（算导版）

cjb中的cjb的数据结构
相当于平衡二叉树的扩展版，一个节点的分叉数[t-1,2t-1)，通过多分叉限定了搜索范围区间，相当于每个节点对数据范围分块，区域块与区域块间秉承树结构的搜索树，美称“多路归并搜索树”。
发明这种算法是因为硬盘的磁头移动速度非常慢，所以锁定了一段磁道尽量多读取一段范围的数据，通过B树这种慢但存储范围巨大的数据结构存储磁盘读出的内容，这样以后再次访问磁盘这段空间可以在B树上查找（根据空间局部性原理，这块磁盘内容很可能再次用到）。。相当于牺牲时间换空间的平衡树，所以基本只应用在文件索引、磁盘访问、数据库上这种存储按块（页）、各种原因需一次读取相当多数据的情况，在算法竞赛上可谓是毫无卵用了。。

插入删除查找复杂度均为 ，隶属平衡树家族，当节点上下界因子t取2时就进化成了平衡二叉树。

插入卫星数据要分裂满节点，删除卫星数据要合并节点，编写难度在平衡树家族中位于中等偏上级别，个人感觉实现上略难于红黑树。

删除操作性质维护操作：
1、如果关键字k在节点x中，且x为叶节点，则从x中删除k
2、如果k在节点x中，且x为内部节点，则做以下操作:
a.节点x前于k的子节点y至少包含t个关键字，则找出k在以y为根的子树的前驱k',递归删除k',并在x中用k'代替k
b.如果y有少于k个关键字，则检查节点x中后于k的子节点z,如果z至少包含t个关键字,则找出k在以z为根的子树中的后继k'，递归删除k'，并在x中用k'代替k。
c.否则如果y和z都只含有t-1个关键字，则将k和z的全部合并至y，这样x失去了k和指向z的指针，并且y现在包含2t-1个关键字，然后释放z并递归地从y中删除k。
3、如果关键字k不在内部节点x中，则确定必包含k的子树的根x.ci（如果k确实在树中）。如果x.ci只有t-1个关键字，则执行3a或3b来保证降至一个至少包含t个关键字的节点。
a.如果x.ci只含有t-1个关键字，但其相邻兄弟至少含有t个关键字，则将x中的某一个关键字降至x.ci中，将x.ci的相邻左或右兄弟的一个关键字升至x，将该兄弟中的相应孩子指针移到x.ci中，这样使得x.ci增加了一个额外的关键字。
b.如果x.ci及x.ci的所有相邻兄弟只包含t-1个关键字，则将x.ci与一个兄弟合并，即将x的一个关键字移至新合并的节点，使其成为该节点的中间关键字。

#include<stdio.h>
const int N1=10;
const int N=1e5+5;
struct node
{
    int size;
    long long num[N1];
    int net[N1+2];
    short leaf;
}B[N+5];
int qos=1;//目前分配节点到的位置，线性分配 
int t=4;
int root;
struct pos
{
    int node_id;
    int pos_id;
    pos(int a=0,int b=0)
    {
        this->node_id=a;
        this->pos_id=b;
    };
};

inline void disk_read(int x,int arr)
{}
inline void disk_write(int x)
{}
inline void free(int x)
{}

pos b_search(int x,int k)
{
    int i=1;
    while(i<=B[x].size&&k>B[x].num[i])
    i++;
    if(i<=B[x].size&&k==B[x].num[i])
    {
        return pos(x,i);
    }
    else if(B[x].leaf)
    return pos(-1,-1);
    else {
        disk_read(x,B[x].net[i]);
        return b_search(B[x].net[i],k);
    }
}

void b_create()
{
    B[1].leaf=1;
    B[1].size=0;
    root=1;
    disk_write(1);
}

void b_split(int x,int i)//B树分裂 
{
    int z=++qos;
    int y=B[x].net[i];
    B[z].leaf=B[y].leaf;
    B[z].size=t-1;
    for(int j=1;j<=t-1;j++)//1 2 3-4-5 6 7
        B[z].num[j]=B[y].num[t+j];
    if(!B[y].leaf)
        for(int j=1;j<=t;j++)
            B[z].net[j]=B[y].net[t+j];
    B[y].size=t-1;
    for(int j=B[x].size+1;j>=i+1;j--)
    B[x].net[j+1]=B[x].net[j];
    B[x].net[i+1]=z;
    for(int j=B[x].size;j>=i;j--)
    B[x].num[j+1]=B[x].num[j];
    B[x].num[i]=B[y].num[t];
    B[x].size++;
    disk_write(y);
    disk_write(z);
    disk_write(x);
}

void b_insert_nonfull(int x,int k)//insert辅助过程 将关键字插入节点x，要求调用时x是非满的 
{
    int i=B[x].size;
    if(B[x].leaf)
    {
        while(i>=1&&k<B[x].num[i])
        {
            B[x].num[i+1]=B[x].num[i];
            i--;
        }
        B[x].num[i+1]=k;
        B[x].size++;
        disk_write(x);
    }
    else {
        while(i>=1&&k<B[x].num[i])
        i--;
        i++;
        disk_read(x,i);
        if(B[B[x].net[i]].size==2*t-1)
        {
            b_split(x,i);
            if(k>B[x].num[i])//合并提上来了一个分割点，和这个提上来的比较来确定插入位置 
            i++;
        } 
        b_insert_nonfull(B[x].net[i],k);
    } 
}

void b_insert(int k)//插入处理根节点 
{
    int r=root;
    if(B[r].size==2*t-1)
    {
        int s=++qos;
        root=s;
        B[s].leaf=B[s].size=0;
        B[s].net[1]=r;
        b_split(s,1);
        b_insert_nonfull(s,k);
    }
    else b_insert_nonfull(r,k);
}

void b_merge(int x,int i,int y,int z)//b树合并
{
    B[y].size=2*t-1;
    for(int j=t+1;j<=2*t-1;j++)
        B[y].num[j]=B[z].num[j-t];
    B[y].num[t]=B[x].num[i];
    if(!B[y].leaf)
    for(int j=t+1;j<=2*t-1;j++)
    B[y].net[j]=B[z].net[j-t];
    for(int j=i+1;j<=B[x].size;j++)
    B[x].net[j]=B[x].net[j+1];
    B[x].size--;
    free(z);
    disk_write(x),disk_write(z),disk_write(y);
}

long long b_pre(int x)
{
    int i=B[x].size;
    while(!B[x].leaf)
    {
        disk_read(x,i+1);
        x=B[x].net[i+1];
        i=B[x].size;
    }
    return B[x].num[i];
}

long long b_suc(int x)
{
    while(!B[x].leaf)
    {
        disk_read(x,1);
        x=B[x].net[1];
    }
    return B[x].num[1];
}

void b_shift_right(int x,int i,int y,int z)
{
    B[z].size++;
    int j=B[z].size;
    while(j>1)
    {
        B[z].num[j]=B[z].num[j-1];
        j--;
    }
    B[z].num[1]=B[x].num[i];
    B[x].num[i]=B[y].num[B[y].size];
    if(!B[z].leaf)
    {
        j=B[z].size;
        while(j)
        {
            B[z].net[j+1]=B[z].net[j];
            j--;
        }
        B[z].net[1]=B[y].net[B[y].size+1];
    }
    B[y].size--;
    disk_write(x),disk_write(y),disk_write(z);
}

void b_shift_left(int x,int i,int y,int z)
{
    B[y].size++;
    B[y].num[B[y].size]=B[x].num[i];
    B[x].num[i]=B[z].num[1];
    B[z].size--;
    int j=1;
    while(j<=B[z].size)
    {
        B[z].num[j]=B[z].num[j+1];
        j++;
    }
    if(!B[z].leaf)
    {
        B[y].net[B[y].size+1]=B[z].net[1];
        j=1;
        while(j<=B[z].size+1)
        {
            B[z].net[j]=B[z].net[j+1];
            j++;
        }
    }
    disk_write(x),disk_write(y),disk_write(z);
}

int fl;//是否删除失败 
void b_delete_nonnull(int x,int k)
{
    int i=1;
    if(B[x].leaf)//1
    {
        while(i<=B[x].size&&k>B[x].num[i])
        i++;
        if(k==B[x].num[i])
        {
            for(int j=i+1;j<=B[x].size;j++)
            B[x].num[j-1]=B[x].num[j];
            B[x].size--;
            disk_write(x);
        }
        else {
            fl=1;
        }
    }
    else {
        while(i<=B[x].size&&k>B[x].num[i])
        i++; 
        disk_read(x,i);
        int y=B[x].net[i];
        int z=0;
        if(i<=B[x].size)
        {
            disk_read(x,i+1);
            z=B[x].net[i+1];
        }
        if(k==B[x].num[i])//2
        {
            if(B[y].size>t-1)//2a
            {
                long long k1=b_pre(y);
                b_delete_nonnull(y,k1);
                B[x].num[i]=k1;
            }
            else if(B[z].size>t-1)//2b
            {
                long long k1=b_suc(z);
                b_delete_nonnull(z,k1);
                B[x].num[i]=k1;
            }
            else {//2c
                b_merge(x,i,y,z);
                b_delete_nonnull(y,k);
            }
        }
        else {//3
            int p=0;
            if(i>1)
            {
                disk_read(x,i-1);
                p=B[x].net[i-1]; 
            }
            if(B[y].size==t-1)
            {
                if(i>1&&B[p].size>t-1)//3a
                    b_shift_right(x,i,p,y);
                else if(i<=B[x].size&&B[z].size>t-1)//3a
                    b_shift_left(x,i,y,z);
                else if(i>1)//3b
                {
                    b_merge(x,i,p,y);
                    y=p;
                }
                else b_merge(x,i,y,z); 
            }
            b_delete_nonnull(y,k);
        }    
    }
}

void b_delete(int k)
{
    int r=root;
    if(B[r].size==1)
    {
        disk_read(r,1),disk_read(r,2);
        int y=B[r].net[1];
        int z=B[r].net[2];
        if(B[y].size==B[z].size==t-1)//2c or 3b
        {
            b_merge(r,1,y,z);
            free(r);
            b_delete_nonnull(y,k);
        }
        else b_delete_nonnull(r,k);
    }
    else b_delete_nonnull(r,k);
} 

int main()
{

} 
/*
测试程序
    b_create();
    for(int i=1;i<10;i++)
    b_insert(i*2+1);
    for(int i=1;i<=30;i++)
    {
        pos t=b_search(root,i);
        printf("%d %d %d\n",i,t.node_id,t.pos_id);
    }
    b_delete(3);
    b_delete(7);
    for(int i=1;i<=30;i++)
    {
        pos t=b_search(root,i);
        printf("%d %d %d\n",i,t.node_id,t.pos_id);
    }
*/