NTFS文件组织是由很多B树(并非B+树)构成（转） [复制链接]

初学NTFS时，看到很多资料都说NTFS是B+树，甚至某些牛书都说NTFS是B+树，
譬如：Microsoft Windows Internals 中文名：深入解析Windows操作系统。
初学者甚至认为整个卷的所有文件是由B+树组织的。

这样会让学习走入误区，浪费了很多时间。正确理解NTFS文件组织对软件开发者是有帮助的。
这里是我对NTFS的B树结构的理解，以供学习者参考：

（1）NTFS是B树结构，这棵B树存储的是某个文件夹（设该文件夹的文件名为Folder0）下的所有直接子文件。
（注意，是直接子文件。若有Folder0\Afolder\b.txt，则此B树中仅存储文件夹Afolder，而不存储b.txt。
如果需要访问b.txt，应该从本B树中获得Afolder的文件参考号去访问MFT中的Afolder，进而从Afolder的
B树中获得b.txt）

注意：NTFS是由很多B树组成，每个文件夹都可能有一个B树记录它的所有直接子文件。这里说的是可能，
因为有的文件夹下的直接子文件比较少，在其索引根属性里就足以记录它的所有直接子文件。

（2）为什么是B树而不是B+树？
B树和B+树都维护了一个数据项的集合，NTFS中的数据项就是指文件，这里具体的：Folder0下的所有直接子文件。
B+树数据结构是在B树基础上改进的。B+树的数据项全部存储于叶子结点块中，相邻的结点用双链表
链接，B+树的内部结点不包含数据项，仅包含索引信息。因此B+树支持快速的在子结点中遍历的范围查询。

然而，B树的数据项在树的内部结点和叶子结点都有，B树叶子结点仅包含部分数据项。

（3）不同与经典的B数结构。
大家都知道，B树中一个结点块由连续的等长数据项组成，而NTFS的索引入口结构作为结点的数据项是不等长的。
传统的B树在块内搜索时支持二分查找，而NTFS中块内查找文件要顺序访问索引入口结构。假设一个块长为4KB=4096B。
一个索引入口结构（包含文件名结构）视文件名长短不一，最少是96B。并且块中还存在其他结构。
因此，一个索引块最多包含大约40个文件。因此块内没有必要进行二分查找。而文件查找的瓶颈在与读取磁盘块。

（4）访问目录下的所有子文件
如果NTFS是B+树，我们访问特定目录下的所有直接子文件，只需要顺序考察所有叶子结点块就够了；
但是NTFS是B树，访问特定目录下的所有直接子文件无法直接考察叶子结点（因为：1.有些文件不在叶子结点中 2.没有叶子结点块间的链接支持）
而访问方法可以从根结点开始进行深度优先遍历