Most programmers are at at least passingly famiIiar with the data structure known as a binary tree. Binary trees are a technique for imposing a logical ordering on a collection of data items by means of pointers, without regard to the physical order of the data. In a simple binary tree, each node contains some data, including a key value that determines the node's logical position in the tree, as well as pointers to the node's left and right sub trees. The node that begins the tree is known as the root: the nodes that sit at the ends of the tree's branches are sometimes called the leaves. To find a particular piece of data, the binary tree is traversed from the root. At each node, the desired key is compared with the node's key: if they don't match, one branch of the node's sub tree or another is selected based on whether the desired key is less than or greater than the node's key. This process continues until a match is found or an empty sub tree is encountered (see Figure A). Such simple binary trees, although easy to understand and implement, have disadvantages in practice. If keys are not well distributed or are added to the tree in a non-random fashion, the tree can become quite asymmetric, leading to wide variations in tree traversal times. In order to make access times uniform, many programmers prefer a particular type of balanced tree known as a B- Tree. For the purposes of this discussion, the important points about a B-Tree are that data is stored in all nodes, more than one data item might be stored in a node, and all of the branches of the tree are of identical length (see Figure B). The worst-case behavior of a B-Tree is predictable and much better than that of a simple binary tree, but the maintenance of a B-Tree is correspondingly more complex. Adding a new data item, changing a key value, or deleting a data item may result in the splitting or merging of a node, which in turm forces a cascade of other operations on the tree to rebalance it. A B+ Tree is a specialized form of B-Tree that has two types of nodes: internal, which only point to other nodes, and external, which contain the actual data (see Figure C). The advantage of a B+ Tree over a B- Tree is that the internal nodes of the B+Tree can hold many more decision values than the intenmediate-level nodes of a B-Tree, so the fan out of the tree is faster and the average length of a branch is shorter. This makes up for the fact that yell must always follow a B+ Tree branch to its end to get the data for which you are looking, whereas in a B-Tree you may discover the data at an interme-diate code or even at the root.
|FAT File System||High Performance File System|
|Maximum filename length||11(in 8.3 format)||254|
|Number of dot (.) delimeters allowed||One||Multiple|
|File Attributes||Bit flags||Bit flags plus up to 64Kb of free-form ASCll of binary information|
|Maximium Path Length||64||260|
|Miniumum disk space overhead per file||Directory entry (32 bytes)||Directory entry (length varies) + Fnode (512 bytes)|
|Average wasted space per file||1/2 cluster (typically 2Kb or more)||1/2 sector (256 bytes)|
|Minimum alocation unit||Cluster (typically 4Kb or more)||Sector (512 bytes)|
|Allocation info for files||Centralized in FAT on home track||Located nearby each file in its Fnode|
|Free disk space info||Centralized in FAT on home track||Located near free space in bitmaps|
|Free disk space described per byte||2Kb ( 1/2 cluster at 8 sectors /clustor)||4Kb (8 sectors)|
|Directory structure||Unsorted linear list, must be searched exhaustivily||Sorted B-Tree|
|Directory Location||Root directory on home track, others scattered||Localized near seek center of volume|
|Cache replacement strategy||Simple LRU||Modified LRU, sensitive to data type and usage history|
|Read ahead||None in MS-DOS 3.3 or earlier, primitive read-ahead optional in MS-DOS 4||Always present, sensitive to data type and usage history|
|Write behind||Not available||Used by default, but can be defeated on per-handle basis|
FIGURE A: To find a piece of data, the binary tree is traversed from the root untill the data is found or an empty subtree is encountered.
FIGURE B: In a balanced B-Tree, data is stored in nodes, more than one data item can be stored in a node, and all branches of the tree are the same length.
FIGURE C: A B+ Tree has internal nodes that point to other nodes and external nodes that contain actual data.