Dia cung - 17 - NTFS - Lập chỉ mục cho các attribute

(tiếp theo của Dia cung 16)



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