数据结构.pptx.pptx

文档介绍：数据结构
2012
APIO授课
清华大学陈可卿
B树
同平衡树、线段树之类的数据结构不同,B树的产生主要应用于外部查找。
1970年,,它是一种平衡的多叉树,称为B树。
B树优劣判断
磁盘存取次数
CPU计算时间
B树的定义
一棵B数是有如下性质的有根树
1)每个节点x有以下域
a. n(x) 表示x中存储的关键字的数量
b. 这n(x)个关键字按照非降序排放
c. isLeaf(x) 表示x是否为叶子
2)每个非叶子节点x,包含有n(x) +1个指向其子节点的指针,son1(x)~sonn(x)+1(x)。
3)节点x的关键字,区分了其子节点的关键字。
B树的定义-2
4)每个叶节点有相同的深度
5)每一个非根节点x,满足t-1≤n(x)≤2t-1。
6)根节点root满足1≤n(root)≤2t-1。
7)对于任意一个B树,t≥2。
B树的性质
B树的基本操作
约定
B树的根一直存在内存中
当根发生变化时,需要对其进行一次DISK-READ/WRITE
所有节点在被当做参数传递之前需要进行一次DSIK-READ/WRITE操作才能考察其内部元素。
B树的查找
需要进行h次磁盘读操作。
CPU操作次数为th。
B树的插入
只有叶子节点可以直接插入
如果叶节点插入后其元素个数超过了2t-1则需要上溢。
key(mid)
/ \
[left .. mid-1] [mid+1 .. right]
这样等于同于,在其父节点上插入一个节点。
B树的插入-2
如果根上溢了,则需要产生一个新根,且树的整体高度加1。