A8站源码交易平台
第一段
为磁盘
或其他直接存取的辅佐存储设备而规划的一种平衡查找树
相似红黑树
但他在下降磁盘IO操作数方面要更好
许多DBS运用B或B变种来存储信息
第二段
B树与红黑树不同处
B树结点可有许多孩子
数个到数千个
即B树的“分支因子”相当大
一般依托于所运用的磁盘单元的特性
B树相似红黑树
便是每颗有n nn个结点的B树高度为O(lgn) O(lgn)O(lgn)
但B树的严峻高度或许比红黑树小许多
因为分支因子大啊
因而可用B树在O(lgn) O(lgn)O(lgn)内完毕一些动态集结的操作
第3段
B树推行了二搜树
图18-1是简略的B树
若内部结点x xx有x.n x.nx.n个关键字
那么x xx有x.n+1 x.{n+1}x.n+1个孩子
x xx中关键字便是分隔点
他把结点x xx所处理的关键字的特征分隔为 x.n+1 x.{n+1}x.n+1个子域
每个子域都由x xx的一孩子呢处理
当在一个B树上查找一关键字
对存储在x xx中的x.n x.nx.n个关键字比较
做出x.n+1 x.n+1x.n+1路的挑选
叶节点域内部结点结构不同，在18.1议论不同
图18-1 关键字为子音字母的B树
一个内部结点x xx包含x.n x.nx.n个关键字
以及x.n+1 x.n+1x.n+1个孩子
叶结点深度相同
浅暗影的结点
是查找字母R时查看果的结点
A8站源码交易平台
第4段
18.1节给B树的准确界说
并证明B树高随他的结点数对数增加
18.2介绍如安在B树查找和刺进一个关键字
18.3 删去操作
咱们需求想清楚为什么
针对磁盘规划的数据结构
不同于
针对随机拜访的主存所规划的数据结构
辅存上的数据结构
第1段
核算机的主存
由硅存储芯片组成
每位的存储价值一般要比
磁存储（磁带磁盘）技能高不止一个数量级
核算机还有根据磁盘的辅存
容量比主存容量高出至少俩数量级
图18-2
第2段
图18-2是典型的磁盘驱动器。
驱动器
一个或多个盘片组成
以一个固定速度
绕着一同的主轴旋转
每个盘的外表掩盖一层可磁化 的物质
驱动器通过磁臂完毕
的磁头来读写磁盘
磁臂可将磁头
向主轴移近或移远
当一个给定的磁头处于间断时
她下面通过的磁盘外表
称为一个磁道
我觉得意思便是磁头不动，磁盘转起来构成的轨迹吧
多个盘片增加的仅仅是磁盘驱动器的容量
而不影响功用
第3段
磁盘比主存廉价容量大
但比主存慢许多
因为有机械运动部分
磁盘有俩机械运动部分
盘片旋转和磁臂移动
编撰本书时分
商用磁盘5400-15000转/分(RPM)
15000RPM服务器
7200RPM台式机
5400笔记本
7200看上去很快
但一圈要8.33ms
比硅存储的常见存储时刻50ns
高5个数量级
也便是说
假定有必要等候一个磁盘转完无缺的一圈
让一个特定的项抵达读写磁头下方
这个时刻内咱们存取主存跨越100 000次
均匀来讲，只需等候半圈
但间隔依然巨大
移动磁臂也要耗时刻哦
编撰本书时分
商用磁盘均匀存取时刻8-11ms
第4段
为了摊还机械移动所花费的等候时刻
磁盘一次存取多个数据页而不是一个
信息被分为一系列持平巨细
的在柱面内
接连呈现的位页面
且为每个磁盘读或写一个或多个无缺的页面
对典型磁盘来说
一个页为211−214 2^{11}-2^{14}2
11
−2
14
字节
一旦读/写磁头正确定位
且盘片现已旋转到所要页面的开端方位
那么对磁盘的读或写就彻底电子化了（除了磁盘的旋转外）
磁盘可以快速的读或写许多的数据
第5段
一般定位到一页信息
并将其从磁盘里读出的时刻
要比
读出信息进行查看的时刻要长的多
因而本章对工作时刻的俩个首要组成部分考虑：
磁盘存取次数
CPU(核算)时刻
第6段
用需求读出或写入磁盘的信息的页数来
衡量磁盘存取次数
注意到磁盘存取时刻不是常量
他依托当时磁道和所需磁道之间的间隔
以及磁盘的初始旋转状况
但我依然运用读或写的页数
作为磁盘存取总时刻的近似
第7段
在一典型的B树运用中
所处理的数据量很大
以至于无法一次装入主存
B树算法将所需页面从磁盘复制到主存
然后将修改正的页面写回主存
任何时分
B树算法都只需在主存中坚持必定数量的页面
因而，主存巨细
并不捆绑被处理的B树的巨细
第8段
设x为指向一个政策的指针
假定他在主存中，那么可像正常相同引证他的特征
如x.key x.keyx.key
但是若在磁盘上
那么在引证他的特征之前，有必要先DISK-READ(x)
x= a pointer to some object
DISK-READ(x)
operations that access and/or modify the attributes of x
DISK-WRITE(x) //omitted if no attributes of x were changed
other operations that access but not modify attributes of x
第9段
任何时分，体系可在主存中保存有限的页数
假定体系不再将运用的页从主存中换出
后边的B树算法会疏忽这一点
第10段
在大多数体系中
B树算法运时首要由他的DISK-READ和DISK-WRITE次数定
so期望这些操作能读或写尽或许多的信息
因而，一个B树结点一般和一个无缺的磁盘页相同大
且磁盘页的巨细捆绑了一个B树结点可有的孩子数
第11段
对存储在磁盘上的大B树
分支因子50-2000之间
详细取决一个关键字相对于一页的巨细
大的分支因子可大大下降树高度
和查找任何一个关键字所需的磁盘存取次数
图18-3闪现了分支因子1001，高2的B树
可存储跨越10亿关键字
不过，因为根节点可耐久保存在主存中
所以在这个树中查找某个关键字
最多只需两次磁盘存取
图18-3
18.1 B 树界说
为简略起见，假定，就像二搜树和红黑树相同
任何和关键字相联系的“卫星数据”
与关键字相同寄存在同一结点
实践只或许为每个关键字寄存一个指针
指向寄存该关键字的卫星数据的磁盘页
这章伪代码都隐含假定
当一个关键字从一个结点移动到另一结点时
无论是与关键字相联系的卫星数据
仍是指向卫星数据的指针
都跟着关键字一同移动
一常见B树变种：B+树
把悉数卫星数据都存在叶结点
内结点只寄存关键字和孩子指针
so最大化了内节点的分支因子
第2段
每个结点x xx有下列特征：
x.n x.nx.n：当时存在结点x xx中关键字个数
x.key1≤⋯≤x.keyx.n x.key_1lecdotsle x.key_{x.n}x.key
1
≤⋯≤x.key
x.n
x.leaf x.leafx.leaf标明此点是否是叶子
每个内部结点x xx还有x.n+1 x.n+1x.n+1个指向其孩子的指针
x.c1,⋯x.cx.n+1 x.c_1,cdots x.c_{x.n+1}x.c
1
,⋯x.c
x.n+1
k1≤x.key1≤k2≤x.key2...kn≤x.keyn≤kx.n+1 k_1le x.key_1le k_2le x.key_2...k_nle x.key_{n}le k_{x.n+1}k
1
≤x.key
1
≤k
2
≤x.key
2
...k
n
≤x.key
n
≤k
x.n+1
叶子深度相同，树高h hh
每个结点所包含的关键字个数有上界和下界。
用个称为B树的最小度数的固定整数
t≥2 t ge 2t≥2来标明这些界
除根结点，每结点有必要有≥t−1 ge t-1≥t−1个关键字
也便是除根节点之外的每个内部结点有≥t ge t≥t孩
假定树非空，根节点至少有一个关键字
每个结点最多2t−1 2t-12t−1个关键字
内部节点最多多少个孩子
结点是满的是啥意思？
t=2 t=2t=2的B树是最简略的。
每个内部结点有2，3，4个孩子
也便是一颗2-3-4树
实践中，t越大，树高就越小
18.2 B 树上根柢操作
本节给
SEARCH
CREATE
INSERT操作细节
用俩约好
B树根一直在主存，无需对根做DISK-READ
但是，当根被改动，需对根做DISK-write
任何被当作参数的结点在被传递之前，
都要对他们先做一次磁盘读
咱们给出的进程都是
单程算法
即它们从树的根开始向下
没有任何回来向上的进程
查找B树
搜B树和搜二搜树很像
只是在每个内结点做x.n+1 x.n+1x.n+1路分支挑选
B-TREE-SEARCH是二搜树上TREE-SEARCH进程的直接推行
输入是个指向某子树根节点x xx的指针和关键字k kk
顶层调用是B-TREE-SEARCH（T.root，k）
假定k kk在B树中，那么回来的是由
节点y yy和使得y.keyi=k y.key_i=ky.key
i
=k组成的(y,i) (y,i)(y,i)
不然回来NIL
B-TREE-SEARCH(x,k)
1 i=1
2 while i<=x.n and k>x.key_i
3 i++ //找到了
4 if i<=x.n and k==x.key_i
5 return (x,i)
6 else if (x.leaf)
7 return NIL
8 else DISK-READ(x,c_i)
9 return B-TREE-SEARCH(x.c_i,k)
1-3找出最小下标i ii，使得k≤x.keyi kle x.key_ik≤x.key
i
若找不到，则i=x.n+1 i=x.n+1i=x.n+1
4-5行查看是否找到关键字，找到则回来
不然，6-9行完毕这次不成功查找（假定是叶子）
或许对孩子节点实施读取磁盘
递归搜素x xx的相应子树
下一段A8站源码交易平台
递归进程所遇到的结点构成了树根向下的简略途径
巴拉巴拉
创空B树
为结构一棵B树T
先用B-TREE-CREATE来创立一个空的根结点
然后调用B-TREE-INSERT来增加新的关键字
这些进程都要用到辅佐进程ALLOCATE-NODE，
他在O(1) O(1)O(1)时刻内为一个新结点分配一个磁盘页
咱们可假定ALLOCATE-NODE所创立的结点并不需求DISK-READ
因为磁盘上还没有该结点的有用信息
B-TREE-CREATE(T)
1 x=ALLOCATE-NODE()
2 x.leaf=TRUE;
3 x.n=0;
4 DISK-WRITE(x);
5 T.root=x;
需求O(1) O(1)O(1)
磁盘操作
CPU时刻
向B树插一关键字
向B树插一关键字比二搜树杂乱得多
像二搜树相同，
要查找刺进新关键字的叶结点的方位
但在B树，
不能简略创立一个新的叶结点，
然后将其刺进，
因为这样得到的树将不再是合法的B树。
相反咱们将新的关键字刺进
一个现已存在的叶结点上。
因为不能将关键字刺进一个满的叶结点，
故引一操作，
将一个满的结点y yy（有2t-1）个关键字
按其中心关键字y.keyt y.key_ty.key
t
割裂为
两各有t−1 t-1t−1个关键字的结点。
中心关键字提升到y yy父结点，
以标识两新树的划分点。
假定y yy的父结点也满，就有必要在刺进新的关键字之前将其割裂
究竟满结点的割裂会沿着树向上传
第二段
与二搜树相同
可在从树根到叶子这个单程
向下进程将一个新的关键字刺进B树
为做这点
并不是比及找出刺进进程中实践要割裂的满结点才做割裂
而是
沿着树往下查找新的关键字所属方位时
就割裂沿途遇到的每个满结点(包含叶结点自身)
每逢割裂一个满结点y yy时，就保证它父结点不满
割裂B树中的结点
