| 词汇 |
这里是一些有帮助的网站，是我写B树代码的时候找到的。
b+树
可固定的顺序 高度平衡 增加/移走键的过程 最短的距离 指针只能够向下
索引根
索引缓冲区
虚拟键
非叶节点键里面的数据ys
在磁盘上指针只能够指向下
我们已经拥有这么多
...
回顾
...
增加规则
找到第一个比新键大一些的键（这很可能需要一个叶节点 ）
在这个键（同一个节点）前面插入新的键，当节点满了的时候
把当前的节点分裂成两个，
把中间键上升到父节点，
现在考虑父节点
结束
删除规则
删除键
如果这个键有孩子的话，
找到后继节点，并把要删除的键移到这个节点
现在来考虑后继的旧节点
结束
当节点不是完全满的时候，
如果一个兄弟有多余的键的话，
借一个；
否则
联合其中的一个兄弟节点
结束
结束
这里是一个例子的集合，覆盖对于B+树的所有机理。这里是一些其他成熟的例子，是一些例子的镜像。
所有的例子的节点都有序号4，比如最多有4个键。如果有更高的次序，那么就需要一些手法。
在每一个例子里面，一个节点包含一个或者更多的键（白色，有名字的）。 每个节点都以一个虚拟键（诊断标记）结束， 这个虚拟键与任何有一般键名字的字典式的比较里面是高位。
| 增加 | 01 02 03 04 05 06 07 08 09 10 11 12 13 14 | |
| 删除 | 01 02 03 04 05 06 07 |
这里是一幅关于flatcap的图片描述使用ddd（数据显示调试器）调试代码的情景 .
这里是在IRC上关于NTFS的一个讨论备忘录。
| flatcap | 嗨 _Oracle_ |
| _Oracle_ | 咳，好 |
| flatcap | 我能为你做点什么吗？ |
| _Oracle_ | 我想知道NTFS里面关于B+树的一些知识 |
| _Oracle_ | 他们看起来有一点落后，至少不是我认为的那样：） |
| flatcap | 他们做了一些奇怪的工作，但是对文件系统来说是完美的。 |
| _Oracle_ | 不，我是说他们的在磁盘上的表示 |
| _Oracle_ | 他们有虚拟节点的排序吗？ |
| flatcap | NTFS里面的树并不都是合适的B+树 |
| flatcap | 一个虚拟键 |
| _Oracle_ | 那正是我希望听到的 |
| flatcap | （今天早上思考还是有一点艰难，我不能够忍受：-） |
| _Oracle_ | 没问题 ;-) |
| flatcap | 树由节点组成，节点包含键 |
| flatcap | 那些键在实际的（理想的）b+树中仅仅是分离者，并且数据仅仅存储在叶子节点中。 |
| _Oracle_ | 是的 |
| _Oracle_ | 在NTFS里面一个节点多大？我的意思是说在这里多少键才合适。 |
| flatcap | 每个索引记录是4k，并且你能够在里面得到10文件名 |
| flatcap | 但是...，那依靠文件名的长度 |
| _Oracle_ | 我认为在b+树里面节点包含键的数目是固定的？ |
| flatcap | 呵呵，一般是 |
| flatcap | NTFS里面的键数一般包含数据和指向孩子的指针 |
| _Oracle_ | 我也注意到了 |
| AntonA | 应该加一条：一个2k大小的索引记录也被认为是奢侈的-对我来说 (-: |
| _Oracle_ | 真的？ |
| _Oracle_ | 什么系统？ |
| AntonA | NT4 |
| flatcap | 因为这里孩子比键更多， 于是不得不有一个虚拟键（没有数据，但是有孩子） |
| _Oracle_ | 很有趣... |
| AntonA | 一些我的目录（比如c:\winnt和 c:\program files）有2k大小的索引块而其他的目录的有4k。 |
| _Oracle_ | 于是虚拟键总是"最大的"？ |
| flatcap | 是的 |
| _Oracle_ | 我明白了... |
| _Oracle_ | 所以如果那些没有叶子的节点有自己的数据，将不能够构成一棵b-树？ |
| flatcap | 我已经写了一个测试程序去帮助我自己理解这些树，这些树是bitkeeper上面的。 |
| _Oracle_ | 我很想看看 |
| flatcap | 我读了许多网页，并且我认为最近的一个条目是一棵b*树 |
| _Oracle_ | 并且他们跟b-树比较比较起来是多么的不同啊？ |
| flatcap | 一棵b-树维持着最少的1/2节点满（除了根节点外） |
| flatcap | 一棵b*树明显的改变了这些规则，并且保持有2/3的节点是满的 |
| _Oracle_ | 那么这些规则仅仅是改变了两个节点合并成一个节点的方法还是？ |
| flatcap | 准确地 |
| _Oracle_ | hmmm... |
| _Oracle_ | 让我思考一会儿 :) |
| flatcap | 在一棵真正的b+树里面，数据键（叶子）应该也有指针指向下一个叶子（为了更快的顺序访问），但是那可能仅仅是在内存里面是这样的 |
| flatcap | 我将会很快去写下我知道的关于NTFS树的一切 |
| _Oracle_ | 让我看看我是否有那些... |
| _Oracle_ | 索引根指向根的索引缓冲区记录 |
| flatcap | 你可以看我的测试程序: http://linux-ntfs.bkbits.net:8080/tng-support/src/tree |
| _Oracle_ | 每个索引记录包含键，这些键有一些指向文件自身的指针，也有指向一些低值键的指针。 |
| flatcap | 是的 |
| _Oracle_ | 我明白了 |
| flatcap | 索引根活动在MFT记录块里面 |
| _Oracle_ | 耶，这正是我努力想发现的 :) |
| flatcap | 所有其他的（索引缓冲区）都不是常驻的 |
| _Oracle_ | 单个所以记录里面的键的数目完全是灵活的吗？ |
| AntonA | 是的 |
| flatcap | 是的，但是这里有一个最小值 |
| AntonA | 一个最小值？ |
| flatcap | 是的，那是树算法里面的一部分。 |
| AntonA | 可以肯定的是，最小的是一个包含终止入口的节点的非数据索引记录？ |
| _Oracle_ | 最小值是多少？ |
| flatcap | 对b+树来说是1/2，对b*树来说是2/3 |
| flatcap | 仅仅是根节点可能包含更少 |
| _Oracle_ | 哦. |
| _Oracle_ | 是的 |
| AntonA | 那么最后的一个节点呢... |
| flatcap | 为了保持这个规则，这些键被移走 |
| flatcap | 甚至后一个节点将会有"正确的数字"在里面 |
| AntonA | 那将意味着在一个真正的大目录里面删除一个文件将会花费几个小时？ |
| flatcap | 不，你可能会那样想，但是平衡并不影响许多其他的节点 |
| flatcap | 如果这棵树有4层（NTFS说有5~10个文件），你将会仅仅被改变4个索引记录 |
| flatcap | 当我有时间的时候（可能明天），我将会画更多的图 |
| _Oracle_ | 我将会很有兴趣去读 |
| flatcap | 你在我们的邮件列表里面吗？_Oracle_ |
| _Oracle_ | 什么邮件列表？（我...没有） |
| AntonA | 主要吸引我的问题是：当Windows NTFS发现一棵不平衡树的将会做什么（因为我喜欢弄乱或者我会简单地选择去忽视平衡） |
| flatcap | 呵呵，我憎恨去想这个:-) |
| _Oracle_ | 我将不想在这里了，那是真的 |
| flatcap | chkdsk程序将会试着再使其平衡，你也会发现当文件被创建/删除的时候ntfs.sys将会使之平衡。 |
| _Oracle_ | 我怎样才能够加入到列表中？ |
| flatcap | http://lists.sourceforge.net/lists/listinfo/linux-ntfs-dev |
| AntonA | 哦，当忽视树的存在的时候对于得到目录操作是多么容易啊（显然在他们上的操作是正确的，所以我们不会杀死文件系统） |
| flatcap | 我将会加入邮件列表，并且在这里回答问题e |
| AntonA | 如果windows能够在没有抱怨失败的时候去得到碎片，它将会至少作为一个首先的应用来思考。 |
| flatcap | 是的，可能，但是我想现在知道更多地去建立一些容易关闭的事情 |
| flatcap | 我仅仅想去开始一项大的工程，在这里我能够开始工作，在不会绊倒你的情况下:-) |
| AntonA | 酷 |
| _Oracle_ | 如果你有时间，我还有一些问题想问你。 |
| AntonA | 象我以前说的那样，我将不会在目录附近的任何地方 (-: |
| flatcap | 真的 |
| _Oracle_ | 尽管有很多小的目录 |
