In NTFS, indexes serve as specialized data structures that organize collections of attributes in a strictly collated, sorted order to enable efficient enumeration and rapid binary-search-style retrieval. Among the most prevalent index implementations encountered during forensic analysis of NTFS volumes is the directory index (commonly identified via the $I30 name), wherein multiple $FILE_NAME attributes—each encapsulating filename metadata, parent MFT references, timestamps, and namespace information—are embedded as index entries.
Directories are explicitly indexed to support high-performance lookups and ordered directory listings, with their contents maintained as a balanced B-tree (or B+ tree variant) structure. Entries are collated lexicographically according to defined collation rules (typically case-insensitive Unicode filename ordering), ensuring alphabetical sequencing. The tree itself consists of hierarchically linked nodes, beginning with a root node (resident in the $INDEX_ROOT attribute) that branches into child nodes stored in index records within the non-resident $INDEX_ALLOCATION attribute (typically 4 KB buffers), with a $BITMAP attribute tracking allocated index buffers. This architecture minimizes disk I/O for name-based searches and preserves forensic artifacts such as deleted entries in slack space until overwritten.
 |
| Figure 1: A tree with ten nodes |
In the context of NTFS directory index analysis, consider a representative B-tree (or B+ tree variant) structure as depicted in Figure 1(A), wherein node A functions as the root node resident within the $INDEX_ROOT attribute of the parent directory’s MFT record. Node A maintains references to child nodes B and C, while node B further descends into subordinate nodes D and E. In forensic terminology, a parent node denotes any internal node containing index entries that reference one or more child nodes via Virtual Cluster Numbers (VCNs) pointing into the $INDEX_ALLOCATION attribute. Conversely, a child node is any subordinate node referenced by a parent.
Leaf nodes are terminal nodes devoid of child pointers (flag 0x02 in the index entry header), exemplified here by nodes F, G, H, I, and J; these typically house the bulk of the sorted $FILE_NAME index entries. Nodes sharing a common parent are designated siblings. The depth of a node corresponds to the number of edges along the unique path from the root to that node, while the height of a node is the length of the longest downward path to a leaf (with all leaves conventionally at height 0, their immediate parents at height 1, and so forth). The illustrated structure exemplifies a binary tree, wherein each internal node is constrained to a maximum of two children—though NTFS directory indexes generalize this to multi-way B-trees capable of holding dozens of variable-length index entries per node (typically within fixed-size 4 KiB index records).
Figure 1(B) illustrates the same tree populated with sortable key values. Traversal for value lookup initiates at the root node and proceeds via ordered comparison: if the target key is lexicographically smaller than the current node’s key, descent follows the left branch; if larger, the right branch. For instance, locating the key 42 against a root value of 50 directs traversal leftward to 30, then rightward to 35, culminating in a match after a minimal number of comparisons. This logarithmic efficiency stands in stark contrast to a linear scan of an unsorted flat directory structure (as in FAT), which could necessitate sequential examination of every entry—potentially requiring up to n comparisons in a directory of n files.
NTFS leverages this balanced tree organization to drastically minimize disk I/O and buffer reads during filename lookups and directory enumerations. From a digital forensics perspective, understanding these node relationships, slack space within index records, and rebalancing behavior is critical, as deleted index entries often persist in unallocated portions of nodes or $INDEX_ALLOCATION slack until overwritten, providing recoverable artifacts of previously existing files even after directory modifications. Linear indexing, by comparison, would impose prohibitive computational and I/O overhead on the file system.
B-Tree
A B-tree constitutes a self-balancing, multi-way search tree engineered to maintain sorted keys while supporting logarithmic-time searches, sequential access, insertions, and deletions. Unlike binary search trees, which restrict each internal node to a maximum of two children, B-trees permit a significantly higher branching factor. This design is particularly optimized for block-oriented storage subsystems such as magnetic disks and SSDs, where minimizing the number of expensive random I/O operations is paramount. By permitting a large number of children (and thus keys) per node, B-trees maintain a shallow overall height, thereby reducing the depth of traversals and the associated disk accesses required during forensic examination of directory structures.
The order of a B-tree, conventionally denoted as m, represents the maximum number of children any single node may possess, rendering it an m-way search tree governed by the following invariants critical to NTFS index analysis:
- All leaf nodes reside at the identical level, guaranteeing perfect balance, uniform tree height, and predictable O(log n) performance irrespective of directory size.
- Keys within each node are maintained in strictly ascending (lexicographically sorted) order according to the volume’s collation rules.
- Every non-root node maintains between ⌈m/2⌉ and m children (inclusive), ensuring nodes remain at least half-full to optimize space utilization and balance.
- A node possessing k children contains precisely k − 1 keys. Consequently:
- The maximum key capacity per node is m − 1.
- The minimum key capacity for any non-root node is ⌈m/2⌉ − 1.
- The root node is afforded special dispensation: it may contain as few as zero keys (when serving purely as a leaf) or as many as m − 1 keys, and—if non-leaf—maintains a minimum of two children.
Note: The ceiling function ⌈x⌉ yields the smallest integer not less than x (e.g., ⌈3⌉ = 3, ⌈3.35⌉ = 4, ⌈1.98⌉ = 2). In NTFS directory indexes, these properties manifest in variable node sizes (typically 4 KB index records in $INDEX_ALLOCATION), with the root often resident in the compact $INDEX_ROOT attribute. From a digital forensics perspective, awareness of these structural rules is essential when carving slack space, analyzing index record rebalancing after file deletions, or reconstructing timelines of directory modifications, as residual deleted $FILE_NAME entries frequently persist in partially filled or unallocated regions of these nodes.
In digital forensic analysis of file systems, the B-tree (and its prevalent B+ tree variant) constitutes a self-balancing, multi-way search tree optimized for block-oriented storage devices. The structure maintains a root node containing a carefully selected set of ordered separator keys that function as range pivots, effectively partitioning the entire keyspace into balanced subtrees. These pivots are distributed to ensure minimal tree height and equitable load distribution across nodes.
During forensic examination or runtime filesystem traversal, a search for a target inode, filename, or directory entry commences at the root node. Through a limited sequence of intra-node key comparisons, the algorithm either locates the target directly or identifies the precise child pointer leading to the appropriate subtree. This process repeats down the shallow tree levels until the leaf node containing the desired metadata is reached.
Owing to its high branching factor and logarithmic time complexity—typically O(logâ‚™) with a notably small constant—the B-tree architecture delivers markedly superior search performance and predictability compared to sequential scanning of a flat, unordered, or even linearly sorted directory listing. This efficiency is particularly critical in forensic investigations involving large volumes, fragmented storage, or deleted/recovered entries, as it minimizes I/O operations on secondary storage while preserving structural integrity through automated node splitting and merging operations that maintain balance during insertions and deletions. Such properties make B-tree-indexed structures (as implemented in filesystems such as NTFS, ext4, and others) invaluable for rapid artifact location, timeline reconstruction, and comprehensive evidence recovery.
Figure 2 depicts a representative NTFS-style B-tree index wherein the keys consist of filename strings (derived from $FILE_NAME attributes) rather than simple numeric values. The root node (Node A), typically resident within the $INDEX_ROOT attribute, contains three sorted keys and maintains four child pointers leading into subordinate index records. To resolve a lookup for the filename ggg.txt, forensic traversal begins at the root: lexicographic comparison establishes that ggg.txt sorts between eee.txt and iii.txt. The corresponding child pointer is followed to Node C, where the matching index entry is located, demonstrating the efficient, ordered search path inherent to NTFS directory indexes.
 |
| Figure 2: A B-tree with file names as values. |
Insertion and deletion operations introduce additional complexity that is particularly salient in digital forensics. These processes trigger node splitting and merging to preserve B-tree invariants, often leaving recoverable artifacts of prior states in slack space or unallocated index records. Consider a scenario in which each node is capacity-constrained to three filename entries. Upon insertion of a new file jjj.txt, initial placement would append it to Node C immediately after iii.txt (as illustrated in the upper portion of Figure 3). However, this action causes Node C to overflow (now containing four entries), violating the minimum-fill requirements.
 |
| Figure 3: The top tree shows ‘jjj.txt’ added to node C, and the bottom tree is the result of removing node C because each node can have only three names. |
To restore balance, NTFS performs a node split: Node C is divided into two new nodes (F and G), the median key (ggg.txt) is promoted to the parent node, and the remaining keys are redistributed. This operation results in the deallocation of two original nodes and the allocation of five new ones (including updated parent references), as shown in the lower portion of Figure 3. Such rebalancing behavior explains why deleted filename entries in NTFS $I30 indexes are frequently fragmented, duplicated, or displaced into slack space within $INDEX_ALLOCATION buffers. From a forensic standpoint, these dynamics complicate recovery but simultaneously provide rich evidentiary value: remnants of overwritten or deleted files often persist across multiple index nodes until subsequent splits or reallocations fully overwrite them, enabling timeline reconstruction and detection of anti-forensic activity.
 |
| Figure 4: The final state from adding the ‘jjj.txt’ file. |
Deletion operations in NTFS B-tree directory indexes further illustrate the dynamic rebalancing mechanisms that generate recoverable artifacts of evidentiary significance. Consider the removal of zzz.txt from Node E. In this straightforward case, the corresponding $FILE_NAME index entry is simply marked as deleted (via flags in the index entry header) or excised from the sorted list within the node, without necessitating tree-wide structural adjustments. Nevertheless, residual metadata—such as the full $FILE_NAME attribute, timestamps, and MFT record references—frequently persists in the node’s slack space or unallocated regions until subsequent writes overwrite it, offering forensic examiners a valuable source for recovering evidence of deleted files.
A more intricate deletion occurs with the removal of fff.txt. Here, Node F is left under-populated (potentially violating the minimum occupancy rule of ⌈m/2⌉ children/keys), triggering a rebalancing operation. To restore compliance with B-tree invariants, the file system performs a rotation or redistribution: the key eee.txt is moved from an adjacent node (e.g., Node I) into Node F, while bbb.txt is shifted from Node B to Node I. These localized adjustments propagate as needed to maintain the critical property that all leaf nodes reside at uniform depth from the root (H), preserving the tree’s logarithmic efficiency and balance (as depicted in Figure 5).
From a digital forensics perspective, such rebalancing during deletions is of paramount importance. It disperses remnants of deleted entries across multiple index records, creates opportunities for carving in slack space within $INDEX_ALLOCATION buffers, and can leave “ghost” entries that survive until the nodes are fully reallocated or compacted. Analysts must therefore carefully parse index headers, bitmap attributes, and node occupancy states when reconstructing directory timelines or identifying anti-forensic tampering.
 |
| Figure 5: Tree after deleting the ‘zzz.txt’ file and the ‘fff.txt’ file. |
Following the rebalancing operation precipitated by the deletion of fff.txt, Node B retains the index entry for bbb.txt within its unallocated (slack) space. The entry was not purged but merely relocated to Node I as part of the key redistribution necessary to maintain minimum node occupancy and tree balance. Consequently, automated forensic carving tools that scan $INDEX_ROOT and $INDEX_ALLOCATION attributes may erroneously flag bbb.txt as a deleted file, even though the file itself was never deleted—only its index reference was migrated during the B-tree maintenance routine.
This phenomenon underscores a key consideration in NTFS directory index forensics: apparent “deleted” filename artifacts frequently arise from legitimate structural reorganizations rather than actual file system deletions. Examiners must correlate such entries against MFT record status, parent directory timelines, and adjacent node contents to differentiate true deletions from rebalancing artifacts, thereby avoiding false positives during recovery and timeline reconstruction.
As previously noted, B-trees are purpose-engineered for block-storage devices that perform large-granularity reads and writes. In production file systems and databases, however, the textbook B-tree is rarely implemented in its pure form. The variant predominantly encountered—and the one utilized by NTFS for its directory indexes—is the B+tree.
NTFS directory indexes (the $I30 index materialized through the $INDEX_ROOT and $INDEX_ALLOCATION attributes) employ a structure that closely conforms to B+tree semantics. Mastery of this distinction is essential for accurate parsing, carving, and interpretation during digital forensic examinations of NTFS volumes.
The fundamental divergence between a classic B-tree and a B+tree concerns data placement. In a conventional B-tree, both internal (non-leaf) nodes and leaf nodes may store full keys together with associated data records or direct pointers to records. Consequently, evidentiary content can reside at any level of the tree. In contrast, a B+tree strictly confines all data records to the leaf nodes. Internal nodes contain only separator keys (which may be duplicated from leaf entries) and child pointers, functioning purely as navigational guides that delimit key ranges for subtree traversal. These internal keys are redundant from a storage perspective, as the authoritative records are always located exclusively at the leaf level.
Both structures generalize binary search trees by permitting nodes to hold multiple keys and more than two child pointers, with each pointer defining an exclusive key sub-range. NTFS derives substantial performance gains from this B+tree-like organization: because internal nodes do not carry full $FILE_NAME attributes, a greater density of keys can be packed into each fixed-size index record (commonly 4 KiB). This yields a shallower tree height, fewer disk I/O operations, and accelerated name lookups and directory enumerations.
From a digital forensics viewpoint, this design has direct implications. All records of evidentiary value—the complete $FILE_NAME attributes containing filenames, timestamps, sizes, and MFT references—are concentrated in leaf-level index entries. Furthermore, B+tree leaf nodes are typically linked in sorted order, facilitating efficient in-order traversal. NTFS exploits this property to return alphabetically sorted directory listings via a single logical pass over the leaf chain. Had a pure classic B-tree been employed, records would be dispersed across internal and leaf nodes, significantly complicating full directory reconstruction, timeline analysis, and recovery of deleted entries from slack space.
In summary, although NTFS literature and forensic tools frequently describe the structure generically as a “B-tree,” the actual implementation for directory indexing embodies the core optimizations and characteristics of a B+tree. This nuance is critical when interpreting index node headers, analyzing rebalancing artifacts, or carving residual filename entries during incident response and forensic investigations.
NTFS Directory Indexing
With the foundational principles of B-trees (and their B+tree variant) now established, attention can turn to their specific implementation in NTFS indexing. In NTFS, indexes serve as the primary mechanism for organizing filenames and subdirectory references within a directory, enabling rapid logarithmic-time lookups rather than inefficient linear scans across potentially thousands of entries.
Each node within the index tree comprises an ordered sequence of index entries. For standard directory indexes (the $I30 index), the sort key in every index entry is the filename, embodied by a copy of the $FILE_NAME attribute. These entries are stored contiguously within the node and maintained in strict lexicographic (alphabetical) order according to the volume’s collation rules.
The sequence of index entries in any given node is terminated by a dedicated empty index entry (often referred to as the terminator or last entry). This sentinel structure, identified by specific flag bits (typically 0x02 in the index entry header), signals the conclusion of valid entries within that node. It carries minimal overhead and serves as a critical boundary marker during traversal, parsing, and forensic carving operations.
This ordered, terminated layout within $INDEX_ROOT (for small directories) and $INDEX_ALLOCATION records (for larger ones) is fundamental to both operational efficiency and forensic analysis, as it facilitates precise location of active entries while also preserving recoverable remnants of deleted or relocated filenames in the slack space following the terminator.
 |
| Figure 6: NTFS directory structure when indexing in use |
NTFS implements directory index storage through a dedicated triad of attributes resident (or partially resident) within the parent directory’s Master File Table (MFT) record. These attributes—$INDEX_ROOT (type 0x90), $INDEX_ALLOCATION (type 0xA0), and $BITMAP (type 0xB0)—collectively realize the B-tree (B+tree-like) structure and are uniformly referred to as the $I30 index.
It is important to note that $I30 does not correspond to a tangible file or stream on disk; rather, it is the conventional internal name assigned to this index namespace for directory filename lookups.
- $INDEX_ROOT (0x90): Always resident within the MFT record. Contains the root node of the index tree and can accommodate a limited number of index entries for small directories. Serves as the mandatory entry point for all index traversals.
- $INDEX_ALLOCATION (0xA0): Non-resident for larger directories. Stores the subordinate index records (typically fixed 4 KiB buffers addressed by Virtual Cluster Numbers), each containing one or more internal or leaf nodes of the tree.
- $BITMAP (0xB0): Tracks allocation status of the index records within the $INDEX_ALLOCATION stream, indicating which buffers are in use. Essential for identifying unallocated space that may contain residual deleted index entries.
This attribute-based architecture underpins the efficiency of NTFS directory operations while simultaneously providing forensic practitioners with structured locations to carve for deleted filenames, analyze rebalancing artifacts, and reconstruct directory timelines through careful examination of index headers, entry flags, and slack space.
 |
| Figure 7: Data structure of the $INDEX_ROOT attribute |
The root index node (and every subsequent node in the tree) comprises an ordered sequence of index entry structures. Each standard (non-terminator) index entry embeds a complete $FILE_NAME attribute that fully describes a file or subdirectory contained within the parent directory. At its core, every directory index entry encapsulates two primary elements:
- The filename key, consisting of the $FILE_NAME attribute (including the Unicode string, name length, namespace, associated timestamps, allocated/real sizes, and flags).
- The MFT file reference (a 64-bit value encoding the target MFT record number and sequence counter), which functions as a direct pointer to the corresponding MFT record of that file or subdirectory.
Index entries are stored contiguously within the node and maintained in strict lexicographic (alphabetical) order according to the defined collation rules. The sequence is always terminated by a dedicated empty index entry—commonly designated the terminator or last entry. This sentinel structure contains no $FILE_NAME payload or key data; it is identified by specific flag bits (typically indicating end-of-list) and serves as the definitive boundary marker for valid entries within the node.
This tightly specified layout is of high forensic value, as it enables precise parsing of active directory contents while exposing recoverable remnants of deleted or relocated entries in the slack space between the final valid entry and the terminator.
 |
| Figure 8: Data structure for “index entry” (specifically for directory) |
When a directory expands beyond the capacity of the resident $INDEX_ROOT attribute, NTFS transparently allocates a non-resident $INDEX_ALLOCATION attribute (type 0xA0) to accommodate the additional nodes of the B-tree. This attribute stores the overflow index nodes as fixed-size index records (also known as index buffers), which are typically 4 KiB in length and aligned for efficient disk I/O.
In contrast to the always-resident $INDEX_ROOT, the $INDEX_ALLOCATION attribute is invariably non-resident. It adheres to the standard layout of non-resident NTFS attributes, with its content described via a runlist (data runs) that maps virtual cluster numbers (VCNs) to the physical locations of the index records on disk. A companion $BITMAP attribute tracks which of these index records are actively allocated.
For small directories, the $INDEX_ALLOCATION attribute is entirely absent, with the complete index residing within the compact $INDEX_ROOT structure. This graduated design balances performance and storage efficiency while providing forensic investigators with distinct, well-defined locations: the root for initial analysis and the allocation attribute for deeper examination of large directories, including recovery of deleted entries scattered across unallocated index records and slack space. The data structure of the $INDEX_ALLOCATION attribute is shown below.
 |
| Figure 9: Data structure for $INDEX_ALLOCATION attribute |
The $INDEX_ALLOCATION attribute (type 0xA0) is instantiated when a directory’s index exceeds the storage capacity of the resident $INDEX_ROOT attribute. It serves as the repository for the overflow nodes of the B-tree (B+tree-like) structure, persisting these nodes on disk as one or more fixed-size Index Records (also termed index buffers).
Each Index Record embodies a single node within the overall index tree and maintains the identical internal format used in $INDEX_ROOT: an Index Record Header, followed by an Index Node Header, and then a contiguous sequence of Index Entry structures (commonly referred to as $I30 entries in directory indexes). In directory contexts, each standard index entry carries a filename—derived from the embedded $FILE_NAME attribute—as its sorting key, accompanied by the corresponding MFT file reference that links to the target file or subdirectory’s MFT record.
The size of each Index Record is specified in the $INDEX_ROOT header and defaults to 4096 bytes (4 KB) on most NTFS volumes, typically aligning with the file system cluster size for optimal I/O performance. The sequence of entries within every record is strictly sorted and terminated by the standard empty index entry (sentinel).
Collectively, these non-resident Index Records extend the directory index beyond the root, enabling NTFS to maintain logarithmic lookup efficiency and balanced tree properties even for directories containing tens of thousands of entries. For forensic practitioners, this architecture is invaluable: it localizes active directory metadata while leaving recoverable artifacts—such as deleted $FILE_NAME entries and rebalancing remnants—within unallocated portions of index records and associated slack space.
.
 |
| Figure 10: Data structure of Index Record |
From a digital forensics standpoint, the $INDEX_ROOT attribute holds exceptional evidentiary value. As the permanent repository of the directory index root node, it contains the initial segment of the B-tree and, in the case of small-to-medium directories, may encompass the complete set of directory entries without any reliance on the non-resident $INDEX_ALLOCATION attribute.
Each index entry establishes a critical linkage between a human-readable filename (encapsulated in the embedded $FILE_NAME attribute) and the corresponding MFT record via its file reference number. This mapping bridges visible directory listings with the underlying file system metadata, providing investigators with a reliable correlation point.
Of particular forensic interest are the empty index entries (terminators) that demarcate the end of the valid entry list in each node. While they function purely as structural sentinels, the slack space immediately preceding or surrounding them frequently harbors remnants of previously allocated index entries. These orphaned or partially overwritten $FILE_NAME structures often persist across file deletions, node splits, merges, and tree rebalancing operations.
As a result, both the $INDEX_ROOT attribute and the associated index records within $INDEX_ALLOCATION (when present) constitute a rich forensic repository. They enable detailed reconstruction of directory activity, recovery of traces of deleted or overwritten files, establishment of creation/deletion timelines through embedded timestamps, and detection of anti-forensic manipulation attempts that target directory metadata.
To illustrate the practical implementation of tree-based indexing in NTFS, we examine the root directory of a volume. The figure below presents a hexadecimal (hex) dump of the index-related attributes residing in MFT entry 5—the canonical location of the root directory (\)—which houses the foundational structures for directory enumeration and filename resolution.
 |
| Figure 11: INDEX attributes in MFT entry 5 (NTFS volume’s root directory) |
In this forensic analysis, focus is placed on the three core index attributes, commencing with the $INDEX_ROOT attribute. The attribute header is depicted in the image below.
 |
| Figure 12: INDEX_ROOT attribute header |
As illustrated in the figure above, the first four bytes of the attribute header encode the value 0x00000090 (144 in decimal), which unambiguously identifies the attribute as $INDEX_ROOT. The total length of the attribute is 0x00000058 (88 bytes), recorded in bytes at offsets 0x04–0x07 of the header. The content of the attribute commences at relative offset 0x0020 (32 decimal), as specified in bytes 0x20–0x21 of the header. This offset delineates the beginning of the $INDEX_ROOT structure (commonly called the INDEX_ROOT header), which encapsulates the critical metadata and index node descriptors governing the root of the directory B-tree index. The complete data structure is interpreted as follows:
|
Relative offsets |
Description |
Values |
|
0x00-0x03 |
Attribute ID |
0x00000090 |
|
0x04-0x07 |
Length of Attribute |
0x00000058 = 88 (i.e., from absolute byte 0x170-0x1C7 in Figure 11) |
|
0x08 |
Resident/Non-Resident Flag |
0x00 = resident |
|
0x09 |
Length of Name of Attribute |
0x04 = 4 |
|
0x0A-0x0B |
Offset to Name of Attribute |
0x0018 = 24 (i.e., absolute offset 0x170 + 0x18 = 0x188 in Figure 11) |
|
0x0C-0x0D |
Flags |
0x0000 = normal |
|
0x0E-0x0F |
Not Yet Known |
0x0006 = possible ID |
|
0x10-0x13 |
Length of Attribute content |
0x00000038 = 56 (From absolute offset 0x190-0x1C7 in Figure 11) |
|
0x14-0x15 |
Offset to the Start of Attribute content |
0x0020 = 32 (i.e., absolute offset 0x170 + 0x20 368 = 0x190 in Figure 11) |
|
0x16 |
Indexed flag |
0x00 = not indexed |
|
0x17 |
Padding to 8-byte boundary |
0x00 |
Bytes at relative offsets 0x18–0x1F within the attribute contain the index name “$I30” encoded in Unicode.
To carve or extract the raw contents of the $INDEX_ROOT attribute during forensic analysis, tools such as icat (from The Sleuth Kit) can be employed by specifying the attribute type 144 (0x90). The extracted content corresponds precisely to the data shown in Figure 11. Notably, bytes 0x00–0x0F (often highlighted for emphasis) comprise the core INDEX_ROOT header, which provides essential metadata about the indexed attribute type, collation rules, and node parameters.
 |
| Figure 13: INDEX_ROOT attribute content |
Bytes 0x00–0x03 of the INDEX_ROOT header specify the type of the indexed attribute, cross-referenced against the $AttrDef file. In this instance, the value 0x30000000 denotes the $FILE_NAME attribute type.
Bytes 0x04–0x07 encode the collation sorting rule that governs the ordering of subsequent index entries. For $FILE_NAME indexes, the rule applied is COLLATION_FILENAME (0x00000001). The full set of possible collation rules includes:
- 0x00000000 → Binary
- 0x00000001 → File Name
- 0x00000002 → Unicode String
- 0x00000010 → Unsigned Long
- 0x00000011 → SID
- 0x00000012 → Security Hash
- 0x00000013 → Multiple Unsigned Long
This collation metadata is critical for accurate parsing and reconstruction of directory indexes during forensic examinations.
Bytes 0x08-0x0B contain the size of the Index Allocation Entry. The value here of 0x00001000 is equal to 4096 decimal. A scan of the sample volume reveals that “INDX” files, which are directory listings held as non-resident data in blocks on the “user” area of the disk, are 4096 bytes long. Any further space that is required by the file is allocated in blocks of the same size, which may or may not be contiguous.
The byte at offset 0x0C specifies the number of clusters per Index Record. Given the BIOS Parameter Block (BPB) indicates a cluster size of eight sectors (as determined at BPB offset 0x13), the value 0x01 (1 decimal) corresponds to 8 × 512 = 4096 bytes (4 KiB). The remaining bytes at offsets 0x0D–0x0F serve as reserved padding.
The $INDEX_ROOT attribute further embeds an Index Node, which constitutes the root node of the B-tree governing the root directory. This Index Node begins immediately after the $INDEX_ROOT header with an Index Node Header (frequently highlighted for analysis), which defines the structure and layout of the index entries contained within the root.
Bytes at offsets 0x10–0x13 within the Index Node Header record the relative offset (from the start of the node header) to the first index entry. In this case, the value 0x00000010 (16 decimal) indicates that the initial index entry begins at absolute offset 0x10 + 0x10 = 0x20 within the attribute content. Each such entry embeds a full $FILE_NAME structure serving as the sort key.
Bytes at offsets 0x14–0x17 store the total size occupied by the index entries list. The value 0x00000028 (40 decimal) signifies that the entries span 40 bytes from the start of the Index Node Header. Consequently, the final byte of the entries area resides at offset 0x10 + 0x28 - 1 = 0x37, which aligns precisely with the overall attribute length declared in the standard NTFS attribute header. This precise offset arithmetic is essential for accurate manual parsing and automated carving of index entries during forensic analysis.
Bytes at offsets 0x18–0x1B record the allocated size of the index entries area. The value 0x00000028 (40 decimal) indicates that the region dedicated to index entries begins at byte offset 0x20 and extends to byte offset 0x37 (highlighted for reference). In this instance, the allocated space is fully occupied by active index entries.
Bytes at offsets 0x1C–0x1F contain the Index Node flags. This field signals whether the index is “small” (entirely resident within the MFT record, value 0x00000000) or “large” (requiring external index records in $INDEX_ALLOCATION, value 0x00000001). Here, the flag 0x00000001 denotes a large index. Forensic testing reveals that partial directory contents may remain resident in the MFT record regardless of external buffers; the presence of both resident entries and an external allocation stream typically sets this flag to 0x00000001. An empty directory or one with exclusively resident entries will show 0x00000000.
Subsequent index entries within this node can be parsed to extract stored filenames, associated MFT references, and indicators of child nodes (via entry flags). Figure 14 details the index entries present in the $INDEX_ROOT attribute of the root directory.
 |
| Figure 14: Index Entries in $INDEX_ROOT attribute |
The first eight bytes (relative offsets 0x00–0x07) of the index entry contain the MFT file reference for the associated item. Bytes at offsets 0x08–0x09 store the total length of the index entry (here 0x0018, or 24 decimal). Bytes at 0x0A–0x0B indicate the length of the embedded $FILE_NAME attribute. In this instance, the value 0x0000 confirms the absence of a filename payload, identifying the structure as an empty index entry (terminator) used solely for structural delineation.
The byte at offset 0x0C encodes the index entry flags, with the following defined values:
- 0x00 → Node has a child (no end-of-list)
- 0x01 → Child node exists in $INDEX_ALLOCATION
- 0x02 → Last entry in the node
- 0x03 → Last entry with a child node in $INDEX_ALLOCATION
The observed flag value 0x03 represents the bitwise combination 0x01 | 0x02:
- 0x01 indicates the presence of a child node (pointing into the $INDEX_ALLOCATION stream).
- 0x02 marks this as the final entry in the current index node.
These flag combinations are vital for forensic traversal algorithms, enabling accurate navigation of the B-tree while identifying boundary conditions and potential slack space containing prior entries.
The remaining three bytes at offsets 0x0D–0x0F serve as padding/reserved space, marking the conclusion of the Index Entry Header and the transition to any associated content. Because the entry flags indicate the presence of a child node, the final eight bytes of the structure store the Virtual Cluster Number (VCN) of the subordinate index record within the $INDEX_ALLOCATION attribute. In this example, the VCN value of 0 designates the child node located at the first index buffer (VCN 0) in the allocation stream.
If the “Last Entry” flag (bit 0x02) is not set for an index entry in the directory under examination, the structure extends to include the full content following the header, typically encompassing the embedded $FILE_NAME attribute and, when applicable, the child VCN pointer as shown in the table below:
|
Relative byte offset |
Length |
Description |
|
0x00 |
6 BYTES |
MFT record number for file name or unused (index) |
|
0x06 |
WORD |
MFT record sequence number or unused (index) |
|
0x08 |
WORD |
Length of Node Entry |
|
0x0A |
WORD |
Length of content (length of Filename attribute) |
|
0x0C |
BYTE |
Index Flags |
|
0x10 |
6 BYTES |
MFT Record number of the parent directory |
|
0x16 |
WORD |
MFT Record Sequence number of the parent directory |
|
0x18 |
LONGLONG |
File Create time |
|
0x20 |
LONGLONG |
File Modified time |
|
0x28 |
LONGLONG |
MFT Record Modified time |
|
0x30 |
LONGLONG |
File Last Accessed time |
|
0x38 |
LONGLONG |
File Allocated Size |
|
0x40 |
LONGLONG |
File Real Size |
|
0x48 |
DWORD |
File Type Flags |
|
0x4C |
DWORD |
$EA buffer size needed or $Reparse_Point Tag |
|
0x50 |
BYTE |
Filename Length (Number of Unicode characters) |
|
0x51 |
BYTE |
File name type (Namespace) |
|
0x52 |
FileName length * 2 |
File name |
The second attribute under examination is the $INDEX_ALLOCATION attribute, depicted in the figure below. This attribute is present only when the flags field in the $INDEX_ROOT header is set to 0x00000001, indicating that the index maintains child nodes in external allocation records. It is invariably non-resident, with its content described via data runs that map to the on-disk locations of the subordinate index records housing additional nodes of the B+tree (or B-tree variant) implementing the directory index.
 |
| Figure 15: MFT entry 5’s $INDEX_ALLOCATION attribute |
The attribute is identified by the signature 0x000000A0 (160 decimal) at relative offsets 0x00–0x03. Consistent with all NTFS attributes, it begins with a standard Attribute Header whose layout mirrors the one analyzed in the $INDEX_ROOT attribute. The complete data structure is interpreted as follows:
|
Relative offsets |
Description |
Values |
|
0x00-0x03 |
Attribute ID |
0x000000A0 |
|
0x04-0x07 |
Length of Attribute |
0x00000050 = 80 (i.e., from absolute byte 0x1C8-0x217 in Figure 11) |
|
0x08 |
Resident/Non-Resident Flag |
0x01 =non-resident |
|
0x09 |
Length of Name of Attribute |
0x04 = 4 |
|
0x0A-0x0B |
Offset to Name of Attribute |
0x0040 = 64 (i.e., absolute offset 0x1C8 + 0x40 = 0x208 in Figure 11) |
|
0x0C-0x0D |
Flags |
0x0000 = normal |
|
0x0E-0x0F |
Not Yet Known |
0x0008 = possible ID |
|
0x10-0x17 |
Starting VCN |
0x0000000000000000 = 0 |
|
0x18-0x1F |
Last VCN |
0x0000000000000000 = 0 |
|
0x20-0x21 |
Offset to the Data Runs |
0x0048 = 72 (i.e., absolute offset 0x1C8 + 0x48 = 0x210 in Figure 11) |
|
0x22-0x23 |
Compression unit size |
0x0000 = 0 |
|
0x24-0x27 |
Padding to 8-byte boundary |
0x00000000 |
|
0x28-0x2F |
Allocated Size of Attribute |
0x0000000000001000 = 4096 |
|
0x30-0x37 |
Real Size of Attribute |
0x0000000000001000 = 4096 |
|
0x38-0x3F |
Initialized size of Stream |
0x0000000000001000 = 4096 |
|
0x40-0x47 |
Attribute Name |
$I30 |
|
0x48-0x4F |
Data Run Descriptor |
11 01 2C 00 00 00 00 00 |
It should be noted that bytes at offsets 0x36 and 0x37 in Figure 15 appear as 0x05 0x00. These bytes represent the Update Sequence Number (USN) for this sector within the Index Record. Prior to detailed forensic analysis or parsing, they must be substituted with the corresponding values from the Update Sequence Array (USA) located at the beginning of the record. In this specific case, the corrected values are 0x0000, which are reflected in the “Real Size” field of the attribute as presented in the table above. This correction process is a standard requirement when manually dissecting or carving NTFS metadata structures to ensure data integrity.
Next, the extracted data runs are parsed to identify the precise on-disk clusters housing the B+tree sub-nodes of the root directory’s index. The first byte of the data run list is 0x11. This byte is divided into two 4-bit nibbles:
- Lower nibble (0x1) → Length of the run length field (in bytes).
- Upper nibble (0x1) → Length of the starting cluster offset field (in bytes).
This encoding indicates that one byte follows for the run length and one byte for the signed starting cluster offset. The subsequent byte (0x01) specifies a run length of one cluster. The next byte (0x2C, decimal 44) provides the starting Logical Cluster Number (LCN). Thus, the $INDEX_ALLOCATION attribute data begins at cluster 44.
Since only a single run is present and the next byte is the terminator 0x00, the entire attribute is confined to this one cluster. In summary, for this directory, the $INDEX_ALLOCATION attribute occupies solely Cluster 44, which contains the additional index records (sub-nodes) of the B+tree structure.
Accurate decoding of data runs is essential in forensic workflows for mapping virtual index records to physical disk locations and carving residual metadata.
 |
| Figure 16: Data runs in the $INDEX_ALLOCATION attribute |
Next, we obtain and analyze the contents of Cluster 44 which contains one index record or index node. The Figure below shows part of hex dump of Cluster 44.
 |
| Figure 17: Hex dumpof the beginning of Cluster 44 containing INDX header, index node header, and first index entry |
As shown in the figure above, the index record begins with the signature 0x494E4458 (“INDX”) at bytes 0-3, identifying it as an NTFS index record. Bytes 4-5 represent the offset to the Update Sequence Array (0x0028 = 40), and bytes 6-7 represent the size of the Update Sequence Array (0x0009 = 9). Bytes 8-15 indicate the $LogFile Sequence Number (0x0000000000103BF2). Bytes 16-23 represent the Virtual Cluster of the index record in the index allocation (0x0000000000000000). Please refer to Figure 10 for the full data structure. The first 24 bytes constitute the INDX header, which is immediately followed by the index node header. The first four bytes of the index node header contain the offset to the first index entry. In this example, the value 0x00000040 indicates an offset of 0x40 (64 bytes) from the start of the index node header. When combined with the 24-byte INDX header, the first index entry therefore begins at byte offset 0x58 (88 decimal) from the start of the index record.
The first eight bytes of the index entry represent the MFT file reference number associated with the filename stored in the entry. In this case, the value 0x0400000000000000 corresponds to MFT entry 0x000000000004, which maps to the NTFS system file $AttrDef. At offsets 0x08–0x09 within the index entry, the entry length is stored. Here, the value 0x68 indicates a total index entry size of 104 bytes. Offsets 0x0A–0x0B specify the size of the embedded $FILE_NAME attribute, which in this case is 0x52 (82 bytes). Finally, bytes 0x0C–0x0F contain the index entry flags. A value of 0x00000000 indicates that this entry does not point to a child node, meaning it is a leaf entry in the B-tree structure.
The $FILE_NAME structure, which contains the name of the file referenced by the first index entry, begins at byte offset 104. This offset is calculated as 88 + 16, where 88 bytes represent the start of the first index entry and 16 bytes correspond to the size of the index entry header. The first 8 bytes of the $FILE_NAME content (05 00 00 00 00 00 00 05 00) represent the MFT file reference number of the parent directory. The lower six bytes contain the actual MFT entry number, which in this case is 0x000000000005 (5). MFT entry 5 corresponds to the NTFS root directory, confirming that the referenced file resides in the root of the volume.
At byte offset 66 within the $FILE_NAME structure, the file name field begins. NTFS stores filenames in Unicode, using two bytes per character. The value at byte offset 64 (0x08) specifies the length of the filename in characters, which in this case is 8. Following this length field, the Unicode characters representing the filename appear (highlighted by the dotted line in Figure 17). Decoding these characters reveals the filename “$AttrDef”.
In this example, a total of 13 index entries are present. For brevity, we omit a detailed discussion of most of these entries, including $BadClus (second entry), $Bitmap (third entry), $Boot (fourth entry), $Extend (fifth entry), $LogFile (sixth entry), $MFT (seventh entry), $MFTMirr (eighth entry), $Secure (ninth entry), $UpCase (tenth entry), $Volume (eleventh entry), and the root directory (.) entry (twelfth entry). Instead, we proceed directly to the final index entry and examine it in detail, as illustrated in the figure below.
 |
| Figure 18: Hex dump of the ending of Cluster 44 containing the last two index entries |
- File name → canada.txt
- MFT reference number of the file → MFT entry 35
- MFT reference of parent directory → MFT entry 5
- Has child node? → No.
The B-tree index structures for the root directory in our sample image is shown in the figure below. These entries are organized in alphabetical order by the name of the files included.
 |
| Figure 19: B-tree index structures for the root directory |
The third attribute is the $BITMAP attribute. When an index becomes too large to fit in the resident $INDEX_ROOT, NTFS stores additional entries in the $INDEX_ALLOCATION attribute and uses a $BITMAP attribute to track allocation. The $BITMAP attribute maintains a bit-level map in which each bit represents the allocation state of a corresponding index buffer within $INDEX_ALLOCATION, typically 4 KB in size. This structure enables NTFS to efficiently manage index growth and reuse freed index records.
This structure is used by named indexes such as $I30, $O (Object ID), $R (Reparse Points), and the indexes maintained by $Secure. The $BITMAP attribute itself may be resident or non-resident depending on its size, rather than the presence of a stream name. The $BITMAP attribute has a type identifier of 0xBO (176) and is organized by bytes, and
each bit corresponds to an index record.
 |
| Figure 20: MFT entry 5's $BITMAP attribute |
As shown in the figure above, the attribute flags at relative offset 0x08 are set to 0x00, indicating that the attribute is resident. The attribute content begins at a relative offset of 0x0020 (32 decimal), as specified by the value in relative offsets 0x14–0x15 (20 00). The total length of the attribute content is 0x08 bytes, as indicated by relative 0x10–0x13 (08 00 00 00). The attribute content (relative offset 0x32-0x390 is extracted as follows.
 |
| Figure 21: MFT entry 5's $BITMAP attribute content |
Except for the first bit (bit 0) of the first byte, all other bits in the attribute content are zero. This indicates that only the first index node (Index Record #0) is currently in use. It is important to note that a root node always exists in a B-tree, stored in the $INDEX_ROOT attribute; however, the root node is not represented in the $BITMAP. The $BITMAP attribute tracks the allocation status of sub-nodes within the B-tree index only.
As files are added to the directory, the listings are initially built within the MFT record itself. When no further entries can be added because all space within the MFT record has been used, the MFT directory listing is changed from resident to non-resident. When this occurs, the MFT record is truncated, and some of the Index Entries in the Index Root attribute are overwritten by two new attributes which define the external storage: the $INDEX_ALLOCATION attribute and the $BITMAP attribute. It should be noted that, in some cases, directory listings are present both in the MFTrecord itself and in an external “INDX” file. The data between the end of the logical record and the end of the record space is known as MFTRecord Slack. Such data could be of significant value in a forensic investigation, as it may be the only record of the file or files having been present on the machine.
References
- Brian Carrier → File system forensic analysis.
- Xiaodong Lin → Introductory computer forensics.
Post a Comment