B-tree性能
B-tree性能
B-tree有以下特性:
1、关键字集合分布在整棵树中;
2、任何一个关键字出现且只出现在一个结点中;
3、搜索有可能在非叶子结点结束;
4、其搜索性能等价于在关键字全集内做一次二分查找;
5、自动层次控制;
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为:
其中，M为设定的非叶子结点最多子树个数，N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题;
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点;删除结点时，需将两个不足M/2的兄弟结点合并。
B-tree造价信息
B-tree中，每个结点包含:
1、本结点所含关键字的个数;
2、指向父结点的指针;
3、关键字;
4、指向子结点的指针;
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1;非根结点至少有[m/2]([]，向上取整)个子结点，相应的，关键字个数为[m/2]-1~m-1。
鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如:
1、B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。
2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支(称为子树)的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。
B-tree性能常见问题
-
性能数据 进场速度259千米/实用升限15240米航程(空加油)于18530千米作战航程(带8枚近距攻击8枚B83武器重16919千克)(高-高-高)11667千米(高-低-高)8149千米作战航程(...
-
韩国“phyto tree黄瓜胶”最近很火热，最让人爱不释手的地方在于其有着强大的美白补水修复功能。空气的粉尘、大气中的紫外线、化妆品残留等这些无一不在伤害我们的肌肤。您可以找韩国代购买，价格都在30...
-
它是一款采用液化气作为气源的嵌入式燃气灶，其采用了蓝芯旋火技术，能够有效聚中加热，同时还能使火焰完美贴合锅底，充分利用热量，并且采用了双管道进气，燃烧也更加充分，能有效到达节能省气的左右，值得选择。
/* btrees.h */
/*
* 平衡多路树的一种重要方案。
* 在 1970 年由 R. Bayer 和 E. McCreight 发明。
*/
#define M 1
/* B 树的阶，即非根节点中键的最小数目。
* 有些人把阶定义为非根节点中子树的最大数目。
*/
typedef int typekey;
typedef struct btnode { /* B-Tree 节点 */
int d; /* 节点中键的数目 */
typekey k[2*M]; /* 键 */
char *v[2*M]; /* 值 */
struct btnode *p[2*M+1]; /* 指向子树的指针 */
} node, *btree;
/*
* 每个键的左子树中的所有的键都小于这个键，
* 每个键的右子树中的所有的键都大于等于这个键。
* 叶子节点中的每个键都没有子树。
*/
/* 当 M 等于 1 时也称为 2-3 树
* +----+----+
* | k0 | k1 |
* +-+----+----+---
* | p0 | p1 | p2 |
* +----+----+----+
*/
extern int btree_disp; /* 查找时找到的键在节点中的位置 */
extern char * InsValue; /* 与要插的键相对应的值 */
extern btree search(typekey, btree);
extern btree insert(typekey,btree);
extern btree delete(typekey,btree);
extern int height(btree);
extern int count(btree);
extern double payload(btree);
extern btree deltree(btree);
/* end of btrees.h */
/*******************************************************/
/* btrees.c */
#include <stdlib.h>
#include <stdio.h>
#include "btrees.h"
btree search(typekey, btree);
btree insert(typekey,btree);
btree delete(typekey,btree);
int height(btree);
int count(btree);
double payload(btree);
btree deltree(btree);
static void InternalInsert(typekey, btree);
static void InsInNode(btree, int);
static void SplitNode(btree, int);
static btree NewRoot(btree);
static void InternalDelete(typekey, btree);
static void JoinNode(btree, int);
static void MoveLeftNode(btree t, int);
static void MoveRightNode(btree t, int);
static void DelFromNode(btree t, int);
static btree FreeRoot(btree);
static btree delall(btree);
static void Error(int,typekey);
int btree_disp; /* 查找时找到的键在节点中的位置 */
char * InsValue = NULL; /* 与要插的键相对应的值 */
static int flag; /* 节点增减标志 */
static int btree_level = 0; /* 多路树的高度 */
static int btree_count = 0; /* 多路树的键总数 */
static int node_sum = 0; /* 多路树的节点总数 */
static int level; /* 当前访问的节点所处的高度 */
static btree NewTree; /* 在节点分割的时候指向新建的节点 */
static typekey InsKey; /* 要插入的键 */
btree search(typekey key, btree t)
{
int i,j,m;
level=btree_level-1;
while (level >= 0)
{
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k [ i ])
{
btree_disp = i;
return t;
}
if (key > t->k [ i ]) /* i == t->d-1 时有可能出现 */
i++;
t = t->p[ i ];
level--;
}
return NULL;
}
btree insert(typekey key, btree t)
{
level=btree_level;
InternalInsert(key, t);
if (flag == 1) /* 根节点满之后，它被分割成两个半满节点 */
t=NewRoot(t); /* 树的高度增加 */
return t;
}
void InternalInsert(typekey key, btree t)
{
int i,j,m;
level--;
if (level < 0) /* 到达了树的底部: 指出要做的插入 */
{
NewTree = NULL; /* 这个键没有对应的子树 */
InsKey = key; /* 导致底层的叶子节点增加键值+空子树对 */
btree_count++;
flag = 1; /* 指示上层节点把返回的键插入其中 */
return;
}
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k[ i ])
{
Error(1,key); /* 键已经在树中 */
flag = 0;
return;
}
if (key > t->k[ i ]) /* i == t->d-1 时有可能出现 */
i++;
InternalInsert(key, t->p[ i ]);
if (flag == 0)
return;
/* 有新键要插入到当前节点中 */
if (t->d < 2*M) /* 当前节点未满 */
{
InsInNode(t, i); /* 把键值+子树对插入当前节点中 */
flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */
}
else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */
SplitNode(t, i); /* 继续指示上层节点把返回的键值+子树插入其中 */
}
/*
* 把一个键和对应的右子树插入一个节点中
*/
void InsInNode(btree t, int d)
{
int i;
/* 把所有大于要插入的键值的键和对应的右子树右移 */
for(i = t->d; i > d; i--)
{
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/* 插入键和右子树 */
t->k[ i ] = InsKey;
t->p[i+1] = NewTree;
t->v[ i ] = InsValue;
t->d++;
}
/*
* 前件是要插入一个键和对应的右子树，并且本节点已经满
* 导致分割这个节点，插入键和对应的右子树，
* 并向上层返回一个要插入键和对应的右子树
*/
void SplitNode(btree t, int d)
{
int i,j;
btree temp;
typekey temp_k;
char *temp_v;
/* 建立新节点 */
temp = (btree)malloc(sizeof(node));
/*
* +---+--------+-----+-----+--------+-----+
* | 0 | ...... | M | M+1 | ...... |2*M-1|
* +---+--------+-----+-----+--------+-----+
* |<- M+1 ->|<- M-1 ->|
*/
if (d > M) /* 要插入当前节点的右半部分 */
{
/* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,
* 并且为要插入的键值+子树空出位置 */
for(i=2*M-1,j=M-1; i>=d; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
for(i=d-1,j=d-M-2; j>=0; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
/* 把节点的最右子树转移成新节点的最左子树 */
temp->p[0] = t->p[M+1];
/* 在新节点中插入键和右子树 */
temp->k[d-M-1] = InsKey;
temp->p[d-M] = NewTree;
temp->v[d-M-1] = InsValue;
/* 设置要插入上层节点的键和值 */
InsKey = t->k[M];
InsValue = t->v[M];
}
else /* d <= M */
{
/* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */
for(i=2*M-1,j=M-1; j>=0; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
if (d == M) /* 要插入当前节点的正中间 */
/* 把要插入的子树作为新节点的最左子树 */
temp->p[0] = NewTree;
/* 直接把要插入的键和值返回给上层节点 */
else /* (d<M) 要插入当前节点的左半部分 */
{
/* 把节点当前的最右子树转移成新节点的最左子树 */
temp->p[0] = t->p[M];
/* 保存要插入上层节点的键和值 */
temp_k = t->k[M-1];
temp_v = t->v[M-1];
/* 把所有大于要插入的键值的键和对应的右子树右移 */
for(i=M-1; i>d; i--)
{
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/* 在节点中插入键和右子树 */
t->k[d] = InsKey;
t->p[d+1] = NewTree;
t->v[d] = InsValue;
/* 设置要插入上层节点的键和值 */
InsKey = temp_k;
InsValue = temp_v;
}
}
t->d =M;
temp->d = M;
NewTree = temp;
node_sum++;
}
btree delete(typekey key, btree t)
{
level=btree_level;
InternalDelete(key, t);
if (t->d == 0)
/* 根节点的子节点合并导致根节点键的数目随之减少，
* 当根节点中没有键的时候，只有它的最左子树可能非空 */
t=FreeRoot(t);
return t;
}
void InternalDelete(typekey key, btree t)
{
int i,j,m;
btree l,r;
int lvl;
level--;
if (level < 0)
{
Error(0,key); /* 在整个树中未找到要删除的键 */
flag = 0;
return;
}
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k[ i ]) /* 找到要删除的键 */
{
if (t->v[ i ] != NULL)
free(t->v[ i ]); /* 释放这个节点包含的值 */
if (level == 0) /* 有子树为空则这个键位于叶子节点 */
{
DelFromNode(t,i);
btree_count--;
flag = 1;
/* 指示上层节点本子树的键数量减少 */
return;
}
else /* 这个键位于非叶节点 */
{
lvl = level-1;
/* 找到前驱节点 */
r = t->p[ i ];
while (lvl > 0)
{
r = r->p[r->d];
lvl--;
}
t->k[ i ]=r->k[r->d-1];
t->v[ i ]=r->v[r->d-1];
r->v[r->d-1]=NULL;
key = r->k[r->d-1];
}
}
else if (key > t->k[ i ]) /* i == t->d-1 时有可能出现 */
i++;
InternalDelete(key,t->p[ i ]);
/* 调整平衡 */
if (flag == 0)
return;
if (t->p[ i ]->d < M)
{
if (i == t->d) /* 在最右子树中发生了删除 */
i--; /* 调整最右键的左右子树平衡 */
l = t->p [ i ];
r = t->p[i+1];
if (r->d > M)
MoveLeftNode(t,i);
else if(l->d > M)
MoveRightNode(t,i);
else
{
JoinNode(t,i);
/* 继续指示上层节点本子树的键数量减少 */
return;
}
flag = 0;
/* 指示上层节点本子树的键数量没有减少，删除过程结束 */
}
}
/*
* 合并一个节点的某个键对应的两个子树
*/
void JoinNode(btree t, int d)
{
btree l,r;
int i,j;
l = t->p[d];
r = t->p[d+1];
/* 把这个键下移到它的左子树 */
l->k[l->d] = t->k[d];
l->v[l->d] = t->v[d];
/* 把右子树中的所有键值和子树转移到左子树 */
for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--)
{
l->k[ i ] = r->k[j];
l->v[ i ] = r->v[j];
l->p[ i ] = r->p[j];
}
l->p[l->d+r->d+1] = r->p[r->d];
l->d += r->d+1;
/* 释放右子树的节点 */
free(r);
/* 把这个键右边的键和对应的右子树左移 */
for (i=d; i < t->d-1; i++)
{
t->k[ i ] = t->k[i+1];
t->v[ i ] = t->v[i+1];
t->p[i+1] = t->p[i+2];
}
t->d--;
node_sum--;
}
/*
* 从一个键的右子树向左子树转移一些键，使两个子树平衡
*/
void MoveLeftNode(btree t, int d)
{
btree l,r;
int m; /* 应转移的键的数目 */
int i,j;
l = t->p[d];
r = t->p[d+1];
m = (r->d - l->d)/2;
/* 把这个键下移到它的左子树 */
l->k[l->d] = t->k[d];
l->v[l->d] = t->v[d];
/* 把右子树的最左子树转移成左子树的最右子树
* 从右子树向左子树移动 m-1 个键+子树对 */
for (j=m-2,i=l->d+m-1; j >= 0; j--,i--)
{
l->k[ i ] = r->k[j];
l->v[ i ] = r->v[j];
l->p[ i ] = r->p[j];
}
l->p[l->d+m] = r->p[m-1];
/* 把右子树的最左键提升到这个键的位置上 */
t->k[d] = r->k[m-1];
t->v[d] = r->v[m-1];
/* 把右子树中的所有键值和子树左移 m 个位置 */
r->p[0] = r->p[m];
for (i=0; i<r->d-m; i++)
{
r->k[ i ] = r->k[i+m];
r->v[ i ] = r->v[i+m];
r->p[ i ] = r->p[i+m];
}
r->p[r->d-m] = r->p[r->d];
l->d+=m;
r->d-=m;
}
/*
* 从一个键的左子树向右子树转移一些键，使两个子树平衡
*/
void MoveRightNode(btree t, int d)
{
btree l,r;
int m; /* 应转移的键的数目 */
int i,j;
l = t->p[d];
r = t->p[d+1];
m = (l->d - r->d)/2;
/* 把右子树中的所有键值和子树右移 m 个位置 */
r->p[r->d+m]=r->p[r->d];
for (i=r->d-1; i>=0; i--)
{
r->k[i+m] = r->k[ i ];
r->v[i+m] = r->v[ i ];
r->p[i+m] = r->p[ i ];
}
/* 把这个键下移到它的右子树 */
r->k[m-1] = t->k[d];
r->v[m-1] = t->v[d];
/* 把左子树的最右子树转移成右子树的最左子树 */
r->p[m-1] = l->p[l->d];
/* 从左子树向右子树移动 m-1 个键+子树对 */
for (i=l->d-1,j=m-2; j>=0; j--,i--)
{
r->k[j] = l->k[ i ];
r->v[j] = l->v[ i ];
r->p[j] = l->p[ i ];
}
/* 把左子树的最右键提升到这个键的位置上 */
t->k[d] = l->k[ i ];
t->v[d] = l->v[ i ];
l->d-=m;
r->d+=m;
}
/*
* 把一个键和对应的右子树从一个节点中删除
*/
void DelFromNode(btree t, int d)
{
int i;
/* 把所有大于要删除的键值的键左移 */
for(i=d; i < t->d-1; i++)
{
t->k[ i ] = t->k[i+1];
t->v[ i ] = t->v[i+1];
}
t->d--;
}
/*
* 建立有两个子树和一个键的根节点
*/
btree NewRoot(btree t)
{
btree temp;
temp = (btree)malloc(sizeof(node));
temp->d = 1;
temp->p[0] = t;
temp->p[1] = NewTree;
temp->k[0] = InsKey;
temp->v[0] = InsValue;
btree_level++;
node_sum++;
return(temp);
}
/*
* 释放根节点，并返回它的最左子树
*/
btree FreeRoot(btree t)
{
btree temp;
temp = t->p[0];
free(t);
btree_level--;
node_sum--;
return temp;
}
void Error(int f,typekey key)
{
if (f)
printf("Btrees error: Insert %d!\n",key);
else
printf("Btrees error: delete %d!\n",key);
}
int height(btree t)
{
return btree_level;
}
int count(btree t)
{
return btree_count;
}
double payload(btree t)
{
if (node_sum==0)
return 1;
return (double)btree_count/(node_sum*(2*M));
}
btree deltree (btree t)
{
level=btree_level;
btree_level = 0;
return delall(t);
}
btree delall(btree t)
{
int i;
level--;
if (level >= 0)
{
for (i=0; i < t->d; i++)
if (t->v[ i ] != NULL)
free(t->v[ i ]);
if (level > 0)
for (i=0; i<= t->d ; i++)
t->p[ i ]=delall(t->p[ i ]);
free(t);
}
return NULL;
}
/* end of btrees.c */
另外还有一种与此类似的树结构叫B+树，像 Berkerly DB , sqlite , mysql 数据库都使用了B+树算法处理索引。
B+和B-(即B)是因为每个结点上的关键字不同。一个多一个，一个少一个。
对于B+树，其结点结构与B-tree相同，不同的是各结点的关键字和可以拥有的子结点数。如m阶B+树中，每个结点至多可以拥有m个子结点。非根结点至少有[m/2]个子结点，而关键字个数比B-tree多一个，为[m/2]~m。
这两种处理索引的数据结构的不同之处:
1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3。B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时间复杂度对某建成的树是固定的。
B-tree性能文献
结构性能B
质量检测人员结构性能考核试卷 （满分 100分，时间 80分钟） 姓名 考试号 单位 一、单项选择题（每题 1 分，共计 40 分） 1、光纤光栅应变计的允许误差为量程的 。 A、±0.5% B、±1.0% C、±1.5% D、±2.0% 2、垂直裂缝的观测位置应在结构构件的 。 A、拉应力最大区段 B、压应力最大区段 C、拉应力最大区段及薄弱环节 D、压应力最大区段及薄弱环节 2、非实验室条件进行的预制构件试验、原位加载试验等受场地、条件限制时，可采用满足试验要求的 其他加载方式，加载量值的允许误差为 。 A、2.5% B、5% C、7.5% D、 10% 4、结构试验中采用弹簧式测力仪，其最小分度值不应大于仪表量程的 。 A、0.5% B、1.0% C、2.0% D、2.5% 5、量测混凝土结构构件时，对受弯构件当需要量测沿截面高度的应变分布规律时，布置测点数不宜少 于 个。 A
结构性能B卷
- 1 - 第四分册 建筑主体结构工程检测技术 第一篇 主体结构现场检测 3、结构性能模拟试卷（ B卷） 一、填空题（每空 1分，共计 20分） 1. 板、梁和桁架等简支构件，试验时应一端采用 ，另一端采用 。 2. 构件的试验荷载布置应符合 或 的要求。 3. 当试验的构件承受较大集中力或支座反力时，应对支承部分进行 。 4. 荷重块加载适用于 试验。荷重块应按区格成垛堆放， 沿试验结构构件的跨 度 方向的每堆长度 不应大 于试 验结 构构件 跨度的 ；对于跨度为 的试验结构构件，每堆长度不应大于构件跨度的 1/4；堆间宜留 的间隙。 红砖等小型块状材料， 宜 称量；对于块体大小均匀， 含水量一致又经 抽样核实块重确系均匀的小型块材，可按 加载量。 5. 结构试验用的各类量测仪表的量程应满足结构构件 的要求，最大测值不 宜大于选用仪表最大量程的 。 6. 钢筋混凝土构件和允许出现裂缝的
B-tree相关推荐
- 相关百科
- 相关知识
- 相关专栏
- 爱仕达AR-F4012ED
- 立式节能锅炉
- 树形结构
- 冷蒿
- 蜜紫菀
- 伊立浦CFXB40-52(P)
- 五月艾
- 伊立浦RC-EH8(P)
- 前缀码
- Pro\ENGINEERWildfire3.0基础实例
- SKG YD501
- 熵编码
- 最大堆
- 老鹳草
- 松叶蕨
- 前序遍历
- 以大豆油多元醇制备的硬质聚氨酯泡沫塑料的性能
- 乙烯基树脂混凝土电解槽的性能及在湿法冶金中的应用
- 影响常温固化FEVE氟碳涂料耐酸碱性能的因素
- 无收缩预应力混凝土高性能灌浆材料与应用
- 增效剂在水工高性能混凝土中增效机理及其应用
- 再生丁基橡胶-丁基橡胶防水卷材压敏胶的制备及性能
- 单面涂铝PVC塑料吊顶材料燃烧性能的实验
- 一型小水线面双体船的水动力性能与结构设计(英文)
- 应用线路避雷器提高10kV配电线路防雷性能
- 有机硅憎水剂对发泡水泥复合保温板性能的影响_胡君
- 云母/氟磷灰石生物玻璃陶瓷的体内外生物学性能
- 增韧双马来酰亚胺树脂及其玻璃布层压板的制备与性能
- 新型随钻堵漏剂ZTC-1的生产工艺及性能评价
- 支路数对热泵空调中冷凝和蒸发两用换热器性能的影响
- 圆柱支撑中空超高摩尔质量聚乙烯烧结过滤板性能对比
- 球形木质素吸附剂吸附L-天门冬氨酸的性能
最新词条
安徽省政采项目管理咨询有限公司
数字景枫科技发展（南京）有限公司
怀化市人民政府电子政务管理办公室
河北省高速公路京德临时筹建处
中石化华东石油工程有限公司工程技术分公司
手持无线POS机
广东合正采购招标有限公司
上海城建信息科技有限公司
甘肃鑫禾国际招标有限公司
烧结金属材料
齿轮计量泵
广州采阳招标代理有限公司河源分公司
高铝碳化硅砖
博洛尼智能科技（青岛）有限公司
烧结刚玉砖
深圳市东海国际招标有限公司
搭建香蕉育苗大棚
SF计量单位
福建省中亿通招标咨询有限公司
泛海三江
威海鼠尾草
Excel 数据处理与分析应用大全
广东国咨招标有限公司
甘肃中泰博瑞工程项目管理咨询有限公司
山东创盈项目管理有限公司
当代建筑大师
广西北缆电缆有限公司
拆边机
大山槟榔
上海地铁维护保障有限公司通号分公司
甘肃中维国际招标有限公司
舌花雏菊
华润燃气（上海）有限公司
湖北鑫宇阳光工程咨询有限公司
GB8163标准无缝钢管
中国石油炼化工程建设项目部
韶关市优采招标代理有限公司
莎草目
建设部关于开展城市规划动态监测工作的通知
电梯平层准确度
广州利好来电气有限公司
四川中泽盛世招标代理有限公司