NTFS File System (7) INDEX

NTFS 인덱스

---

 NTFS에서는 자료들을 빠르게 검색할 수 있도록 인덱스 구조로 관리하고 있다. 이의 대표적인 예가 바로 디렉터리이며 이러한 인덱스의 구조에 대하여 알아보자. NTFS가 인덱스로 관리하는 데이터는 아래의 표와 같다.

 이러한 인덱스 관리 방법으로는 트리를 사용하는데 NTFS에서 사용하는 B 트리의 형태는 아래의 그림과 같다. 루트 노드는 최상위에 존재하며 시작점이 되는 노드이며 하위의 자식 노드를 가질 때 자신보다 왼쪽은 작은 값, 오른쪽은 자신보다 큰 값이 위치한다. 이를 통해 자신보다 낮은 노드를 찾기 위해선 왼쪽으로 가면 되고 높다면 오른쪽으로 가면 되는 편의성을 갖는다.

 위의 그림과 같이 NTFS의 Index Node는 마지막에 노드의 끝을 알려주는 End of Node가 포함되어 있다. 이러한 End of Node를 제외하고 n개의 Index 엔트리를 담는 인덱스 노드가 가질 수 있는 자식의 노드 수는 n+1개가 되며, 위 그림에선 Root Index Node가 담고 있는 Index Entry는 3개 인 것을 알 수가 있다.

 Index Node는 크게 Index Node Header와 Index Entry로 나눌 수가 있다. 인덱스 엔트리의 크기는 가변적이기에 마지막에 End of Node가 필요한 것이다. 이러한 인덱스 노드는 독립적으로 존재하지 않으며 반드시 $INDEX_ROOT속성이나 $INDEX_ALLOCATION 속성에 속해야 한다. 어떤 노드가 $INDEX_ROOT에 속한다면 그 노드는 index의 최상위 노드(Root Index Node)가 되는 것이다. 최상위 노드를 제외하면 다른 모든 노드들은 $INDEX_ALLOCATION 속성에 속하게 된다.

 인덱스 노드가 $INDEX_ROOT 속성에 존재하는 경우 $INDEX_ROOT 헤더가 index node header 앞에 붙고, $INDEX_ALLOCATION 속성에 존재할 경우 Index Record 헤더가 앞에 붙게 된다. 아래의 그림에서 이를 확인할 수가 있다. $INDEX_ROOT에 속한 경우 $INDEX_ROOT 헤더가 붙는 것을 확인할 수가 있으며 그 자식 인덱스 노드들은 $INDEX_ALLOCATION 속성에 속하기 때문에 Index Record 헤더가 붙는 것을 확인할 수가 있다.

구조

---

 우선 아래의 첫번째 사진은 $INDEX_ROOT에 속한 경우의 구조이며, 아래의 경우 $INDEX_ALLOCATION 속성에 속했을 때의 구조를 나타내고 있다. 두 그림에서와 같이 공통적으로 Index Node Header를 포함하고 있으며 해당 헤더 앞에 각 각 Index Root Header와 Index Record Header가 오는 것을 확인할 수가 있다. 우선 공통적으로 나타나는 Index Node Header의 구조와 Index Entry의 구조에 대하여 먼저 살펴보자.

INDEX NODE HEADER

• Offset to Start of index entry list : 인덱스 엔트리 목록의 시작 위치(첫번째 Index Entry가 있는 위치 값)

• Offset to Endof used portion of index entry list: 인덱스 엔트리의 실제 크기(인덱스 노드 헤더 포함)

• Offset to end of Allocated index entry list buffer : 인덱스 엔트리의 할당 크기(인덱스 노드 헤더 포함)

• Flags

0x00: 인덱스 노드의 자식노드가 없음        0x01: 인덱스 노드의 자식노드가 있음

 Flag를 제외하고 어떤 크기나 위치를 담는 항목으로 해당 인덱스 노드가 담고 있는 Index Entry 중 하나라도 자식을 가진다면 Flags 항목 값은 1로 설정이 된다. 이와 똑같은 의미를 갖는 Flag가 각각의 Index Entry에도 존재하고 있다. 위 4개의 항목 중 2번째와 3번째 항목의 값을 통해 Index Node에서 삭제된 Index Entry의 정보를 조사할 수 있다. 아래의 그림과 같이 실제 크기와 할당된 크기의 차이를 통해서 확인할 수가 있다.

INDEX ENTRY

•File Reference Address for filename : 해당 파일 및 디렉터리의 파일 참조 주소

•Length of this entry : 해당 인덱스 엔트리의 총 크기

•Length of content : 해당 인덱스 엔트리가 담고있는 $FINE_NAME 속성의 크기

•Flags 

0x01: 자식 노드가 존재         0x02: 노드의 마지막 엔트리(End of Node)

•VCN of child node in $INDEX_ALLOCATION 

해당 인덱스 엔트리가 자식노드를 가지는경우 $INDEX_ALLOCATION 속성에 위치한 자식 인덱스 노드의 위치

 위에서 $FILE_NAME Attribute가 되어 있는 이유는 해당 크기가 가변적이기도 하며 End of Node에선 이 항목이 생략되어 있기 때문이다. 마지막 항목의 경우 해당 인덱스 엔트리가 자식 노드를 가질 경우에 이 항목이 존재하는 것으로 이 항목의 위치를 알아내는 방법은 2번째 항목인 'Length of this entry'에서 -8을 하면 된다. 이를 통해 얻은 VCN 값은 $INDEX_ALLOCATION 속성에 담겨 있는 자식 Index Node의 위치 값이다.

INDEX_ROOT Header

•Type of attribute in index : 인덱스 엔트리가 담고 있는 속성 식별값(디렉터리의 경우0x30, $FILE_NAME)

•Collation sorting rule : 인덱스 엔트리가 담고 있는 형식(형식에맞게정렬됨)

0x00: Binary / 0x01: File Name / 0x02: Unicode String / 0x10: Unsigned Long /

0x11: SID / 0x12: Security Hash / 0x13 : Multiple Unsigned Logs

•Size of each index record in bytes : $INDEX_ALLOCATION 속성이 가지는 인덱스 레코드의 바이트 크기

•Size of each index record in Clusters : $INDEX_ALLOCATION 속성이 가지는 인덱스 레코드의 클러스터 크기

 해당 속성은 인덱스의 최상위인 루트에 해당하는 인덱스 노드를 담는 속성으로 인덱스 크기가 작으면 $INDEX_ROOT만으로 인덱스를 구성하고자 한다. 이 경우 거주(Resident) 형식이기 때문에 많은 Index Entry를 담지 못한다. 크기가 점차 커지므로 모두 담지 못할 경우 $INDEX_ALLOCATION 속성을 만들어 커진 인덱스를 관리한다. $INDEX_ALLOCATION 속성이 생기면 Index Record의 할당을 관리하기 위한 $BITMAP 속성도 같이 생긴다.

INDEX RECORD HEADER

•Signature : $INDEX_ALLOCATION의 시그니처(“INDX”)

•Offset to Fixuparray : Fixuparray의 위치

•Number of entries in Fixuparray : Fixuparray에 저장된 항목의 수

•$LogFileSequence Number (LSN) : $LogFile에 존재하는 해당 파일의 트랜잭션 위치 값

•The VCN of this record in the full index stream : $INDEX_ALLOCATION에서 해당 인덱스 레코드가 저장된 위치- Index Record의 시작 VCN

 최상위 인덱스 노드를 제외한 모든 인덱스 노들들은 이 속성에 담기게 된다. 이 속성의 내용은 Index Record라는 구조체들로 구성되며 하나의 Index Record는 하나의 Index Node를 담고 있다. 아래의 그림과 같이 Index Node의 구조는 $INDEX_ROOT의 속성안에 담기는 것과 동일하며 Index Node가 $INDEX_ALLOCATION 속성에 존재할 경우 Index Record라는 구조 안에 존재하게 된다는 것이다.

 마지막 항목의 시작 VCN은 해당 Index record가 $INDEX_ALLOCATION 속성 데이터 내에서 어느 부분에 존재하는지를 알 수 있도록 해주는 항목이다. VCN과 관련하여 아래의 그림을 참고하자.

$BITMAP

 인덱스 레코드의 할당 상태를 관리하기 위한 속성으로 위와 같은 할당 정보를 표현한다. 할당 정보를 관리하는 데이터로는 $MFT와 $INDEX_ALLOCATION이 있으며 위의 그림과 같은 구조를 지닌다. 아래의 그림과 같이 되어있을 경우 1번째와 3번째 MFT Entry가 현재 사용중임을 나타낸다.

정리

---

 NTFS가 인덱스를 관리할 때 3가지 속성을 사용한다고 이야기 하였다. $INDEX_ROOT 속성은 최상위 Index Node를 담고 있는 속성으로 이 속성만으로 구성이 될 수 있는데 이는 '작은 인덱스'라 한다. Index Entry가 너무 적어서 $INDEX_ROOT 속성만으로 충분하기 때문이다. 작은 인덱스의 구조는 아래의 그림과 같다.

 이에 반해 $INDEX_ROOT 뿐만이 아니라 $INDEX_ALLOCATION, $BITMAP 모두 갖춘 인덱스를 큰 인덱스라 하며, 일반적으로 볼륨에 담겨 있는 대부분의 인덱스가 이러한 형태이다. 위의 작은 인덱스 구조에 다른 파일들이 추가되었을 경우에 대하여 알아보자.

우선 $INDEX_ROOT 속성에 있던 BBB.TXT 파일의 Index Entry가 자식 노드인 것을 알 수가 있으며, $INDEX_ALLOCATION, $BITMAP 속성이 추가된 것을 확인할 수가 있다. $INDEX_ALLOCATION 속성이 관리하는 Index Record 2개가 클러스터를 할당 받아 새로 생성되어 그 안에 Root Index Entry를 가지고 있게 된다. EEEEE.TXT 부분을 보게 되면 파일의 Index Entry 2개가 존재하는데 DOS 형식의 이름을 가지지 않은 파일들은 2개의 Index Entry를 가지고 있게 된다. $Bitmap 속성의 경우 각각의 bit들은 Index Record들과 1대 1로 대응한다.

출처 및 참고

http://blog.naver.com/PostView.nhn?blogId=bitnang&logNo=70184788707&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

(FP) NTFS.pdf