📄 index.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link rel="stylesheet" type="text/css" href="../../style/ntfsdoc.css">
<link rel="icon" href="../../style/ntfsicon.png" type="image/png">
<link rel="start" type="text/html" href="../../index.html" title="NTFS Documentation">
<link rel="up" href="../index.html">
<link rel="next" href="../clusters.html">
<link rel="previous" href="../attribute_id.html">
<link rel="contents" href="../../index.html">
<title>B*Trees - NTFS Directory Trees - Conecpt - NTFS Documentation</title>
</head>
<body>
<table border="0" class="toolbar" summary="" cellspacing="0">
<tr>
<td class="toolbar"><div class="toolbar"><a accesskey="1" class="toolbar" href="../../index.html">主页</a></div></td>
<td class="toolbar"><div class="toolbar"><a accesskey="2" class="toolbar" href="../../files/index.html">文件</a></div></td>
<td class="toolbar"><div class="toolbar"><a accesskey="3" class="toolbar" href="../../attributes/index.html">属性</a></div></td>
<td class="toolbar"><div class="toolbar"><a accesskey="4" class="toolbar" href="../../concepts/index.html">概念</a></div></td>
<td class="toolbar"><a accesskey="5" class="toolbar" href="../../help/glossary.html">词汇</a></td>
</tr>
</table>
<h1>概念 - B*树 - NTFS目录</h1>
<a class="prevnext" accesskey="," href="../attribute_id.html">前一页</a>
<a class="prevnext" accesskey="." href="../clusters.html">后一页</a>
<p>
<a class="visible" href="index.html">主页</a>
<a class="visible" href="add.html">增加</a>
<a class="visible" href="del.html">删除</a>
</p>
<h3>参考</h3>
<p>
这里是一些有帮助的网站，是我写B树代码的时候找到的。
</p>
<table border="0">
<tr>
<td><a href="http://tide.it.bond.edu.au/inft320/003/lectures/physical.htm">http://tide.it.bond.edu.au/inft320/003/lectures/physical.htm</a></td>
</tr>
<tr>
<td><a href="http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html">http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html</a></td>
</tr>
<!--
<tr>
<td><a href="http://www.public.asu.edu/~peterjn/btree">http://www.public.asu.edu/~peterjn/btree</a></td>
</tr>
broken
<tr>
<td><a href="http://www.autoobjects.com/Home/Teaching/CmpE_126/CmpE_126_Lectures/B-Tree/b-tree.html">http://www.autoobjects.com/Home/Teaching/CmpE_126/CmpE_126_Lectures/B-Tree/b-tree.html</a></td>
</tr>
-->
<tr>
<td><a href="http://www.fit.qut.edu.au/~maire/baobab/baobab.html">http://www.fit.qut.edu.au/~maire/baobab/baobab.html</a></td>
</tr>
<tr>
<td><a href="http://www.fit.qut.edu.au/~maire/baobab/lecture/index.htm">http://www.fit.qut.edu.au/~maire/baobab/lecture/index.htm</a></td>
</tr>
</table>
<h3>基本术语</h3>
<dl>
<dt>键（Key）</dt>
<dd>一个产生数据的对象</dd>
<dt>叶节点（Leaf）</dt>
<dd>一个没有孩子的键</dd>
<dt>节点（Node）</dt>
<dd>一个键的集合</dd>
<dt>次序（Order）</dt>
<dd>顺序为n的一个节点，最多有n-1个键</dd>
<dt>树（Tree）</dt>
<dd>一个有序的数据结构</dd>
<dt>根节点（Root Node）</dt>
<dd>一个没有父节点的节点</dd>
<dt>中间层（Median）</dt>
<dd>这层每个节点有((n-1)/2)个键</dd>
<dt>兄弟（Siblings）</dt>
<dd>同一个节点里面的两个键，或者两个节点共同一个父节点</dd>
<dt>深度（Depth）</dt>
<dd>在树里面为树的层数，祖父，父亲，孩子 = 3</dd>
<dt>b-树（b-tree）</dt>
<dd>一棵平衡树</dd>
<dt>b+树（b+tree）</dt>
<dd>一棵平衡树，树的节点至少有一半是满的</dd>
<dt>b*树（b*tree）</dt>
<dd>一棵平衡树，树的节点至少有 2/3 是满的</dd>
<!--
<dt>Successor</dt>
<dd>...</dd>
<dt>Deficient Node</dt>
<dd>...</dd>
-->
</dl>
<h3>纵览</h3>
<p>
b+树
</p>
<pre>
可固定的顺序
高度平衡
增加/移走键的过程
最短的距离
指针只能够向下
</pre>
<h3>NTFS 树</h3>
<p>
<pre>
索引根
索引缓冲区
虚拟键
非叶节点键里面的数据ys
在磁盘上指针只能够指向下
我们已经拥有这么多
...
回顾
...
增加规则
找到第一个比新键大一些的键（这很可能需要一个叶节点 ）
在这个键（同一个节点）前面插入新的键，当节点满了的时候
把当前的节点分裂成两个，
把中间键上升到父节点，
现在考虑父节点
结束
删除规则
删除键
如果这个键有孩子的话，
找到后继节点，并把要删除的键移到这个节点
现在来考虑后继的旧节点
结束
当节点不是完全满的时候，
如果一个兄弟有多余的键的话，
借一个；
否则
联合其中的一个兄弟节点
结束
结束
</pre>
</p>
<h3>举例</h3>
<p>
这里是一个例子的集合，覆盖对于B+树的所有机理。这里是一些其他成熟的例子，是一些例子的镜像。
</p>
<p>
所有的例子的节点都有序号4，比如最多有4个键。如果有更高的次序，那么就需要一些手法。
</p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -