Lập chỉ mục (Index) cho các attribute trong hệ thống NTFS
Phần trên đã trình bày những kiến thức cơ bản về B-tree.
Phần này sẽ trình bày cách NTFS sử dụng B-tree để tạo các index cho các
attribute.
Hệ thống NTFS sử dụng B-tree để chứa các attribute (dưới
dạng các danh sách - list). Mỗi nút trong B-tree gồm nhiều index entry. Một index entry gồm phần header và phần
attribute. Entry kết thúc của danh sách là một entry rỗng.
Hình sau minh họa một nút gồm bốn index entry của một thư
mục, mỗi index entry chứa header của entry và attribute $FILE_NAME.
Các nút của B-tree được lưu trữ trong hai loại attribute tại
MFT entry, một là attribute $INDEX_ROOT và hai
là attribute $INDEX_ALLOCATION.
Attribute $INDEX_ROOT là attribute
thường trú (resident), chỉ chứa được một nút với số lượng index entry rất ít. Attribute
$INDEX_ROOT luôn chứa nút gốc (root) của cây chỉ mục (index tree).
Attribute
$INDEX_ALLOCATION là attribute không thường trú (non-resident), chứa được nhiều
nút. Như đã biết, một attribute được chia thành hai phần: attribute header và
attribute content. Với attribute $INDEX_ALLOCATION, phần attribute content được
chia thành các đoạn có kích thước 4 096 byte, gọi là index record. Index record
được sử dụng để chứa các index entry. Các index record được đánh địa chỉ, bắt
đầu từ 0.
Hình dưới đây
minh họa một thư mục có ba index entry trong attribute $INDEX_ROOT và ba index
record trong attribute $INDEX_ALLOCATION, vị trí của các index record bắt đầu
tại cluster 713.
Attribute
$INDEX_ALLOCATION có thể còn không gian trống chưa được dùng bởi các index
record. Hệ thống NTFS sử dụng attribute $BITMAP để quản lý trạng thái sử dụng
các index record và cấp phát không gian đĩa cho các index record. Khi cần tạo
một nút mới cho cây, hệ thống sẽ tham chiếu tới attribute $BITMAP để tìm một
index record còn trống, nếu không tìm được, hệ thống sẽ cấp thêm không gian cho
attribute $INDEX_ALLOCATION.
Mỗi chỉ mục sẽ
được đặt tên riêng, tên này cũng được sử dụng lại trong header của các
attribute $INDEX_ROOT, $INDEX_ALLOCATION và $INDEX_BITMAP thuộc về chỉ mục.
Mỗi index entry
có một “cờ báo” (flag), cho biết index entry này có nút con hay không? Nếu có
nút con, địa chỉ của các index record chứa nút con sẽ được lưu trong index
entry.
Các index entry trong
mỗi nút luôn được sắp thứ tự, nếu giá trị cần tìm nhỏ hơn index entry và index
entry này có nút con, khi đó sẽ thực hiện tìm ở nút con của nó. Nếu gặp entry
trống ở cuối của danh sách, việc tìm sẽ được thực hiện trên các nút con.
Sau đây là một số
ví dụ về chỉ mục.
Ví dụ: một chỉ
mục gồm ba index entry, chứa vừa đủ trong $INDEX_ROOT. Trong trường hợp này hệ
thống chỉ tạo ra $INDEX_ROOT để chứa ba index entry trên và một index rỗng ở
cuối danh sách. Xem hình bên dưới.
Ví dụ: một chỉ
mục gồm 15 index entry, attribute $INDEX_ROOT không thể chứa hết 15 index entry
này. Một index record trong attribute $INDEX_ALLOCATION được sử dụng để chứa
chỉ mục này. Xem hình minh họa bên dưới.
Ví dụ: một index
record đang ở trạng thái đã được lấp đầy bởi các index entry, giả sử cần thêm
index entry vào cây, hệ thống sẽ tạo ra một cây gồm ba nút. Khi đó, cây sẽ gồm
một nút gốc (root node), và hai nút con. Mỗi nút con được lưu trong một index
record riêng tại attribute $INDEX_ALLOCATION. Các entry trong nút $INDEX_ROOT
sẽ có trường để trỏ tới $INDEX_ALLOCATION. Xem hình bên dưới.
------------------------------
Tham khảo
[1] Brian Carrie, File
System Forensic Analysis, Addison Wesley Professional, 2005
----------------------
Cập nhật: 2013/11/15