NTFS에서는 앞 글에서도 언급 했듯이 b-tree 를 사용한다고 했었다.

NTFS는 많은 상황에서 인덱스 구조체를 사용한다. NTFS 인덱스는 정렬된 순서로 저장된 속성들의 모음을 일컫는다.

인덱스가 제일 흔하게 사용되는 것이 디렉토리인데, $FILE_NAME 속성을 포함하기 때문이다.

NTFS에서 인덱스는 이진트리, b-tree로 정렬된다. 이진트리는 자료구조론에서 자주 언급되는 개념 중 하나이기 때문에 여기서 언급은 생략하고 b-tree에 대해서만 설명 하겠다.

b-tree는 이진트리와 유사한 형태이지만, 노드 별로 자식 노드가 2개 이상이다. 

b-tree에는 여러 종류와 규칙이 있지만 여기서는 b-tree에 대해서만 설명 할 것이며 노드 삽입, 삭제에 대해서 이야기 해보도록 하겠다.

b-tree는 기본적으로 아래와 같이 생겼다.

[그림 1 - b-tree 기본 구조]


가칭으로 각 노드에 알파벳 이름을 붙여 놨다. 이제 위 기본 구조를 이용해 삽입, 삭제를 알아보도록 하겠다.

[삽입]
먼저 위 기본 구조에 90이라는 값을 삽입해보자. 90이라는 값을 삽입하려고 시도 할 경우는 아래 순서를 이용한다.

1. 값과 가장 가까운 값이 들어있는 노드를 찾는다. --> 위 기본 구조에서 C 노드가 가장 적합하다.

2. 빈 공간이 있다면 빈 공간에 삽입하고자 하는 값(90)을 삽입한다.

3. 만약 삽입하려 하는 노드에서 원래 있던 값(80)과 삽입하려는 값(90) 중 원래 있던 값이 크다면 삽입하려는 값이 원래 있던 값 앞으로 온다. --> 현재 삽입하려는 값이 원래 있던 값보다 크므로 자리이동 없이 원래 있던 값 뒤에 위치한다.


위 과정을 거치면 아래와 같다.

[그림 2 - 90 값을 삽입한 경우]

이번에는 30이란 값을 삽입해보자. 이번의 경우는 노드가 값으로 꽉 차있을 경우 어떻게 삽입이 되는지를 알아 보는 것이다.
삽입 과정은 아래와 같다.

1. 값과 가장 가까운 값이 들어있는 노드를 찾는다. --> 위 구조에서 B 노드가 가장 적합하다.

2. 노드에 빈공간이 없을 경우 해당 노드를 분열 하여 새로운 노드를 구성한다. --> 노드를 분열한 후 노드에 들어갈 후보 값(10, 20, 30) 중 제일 큰 값을 새로운 노드로 삽입하고, 남은 두 값(10, 20) 값 중 큰 값을 부모 노드로 삽입한다. 마지막으로 남은 값(10)은 원래 노드에 남겨둔다.

3. 노드 분열로 인해 다른 노드가 변경되어 값들이 꽉 차 있다면 해당 값들을 비교하여 정렬한다.


아래는 결과물이다.

[그림 3 - 30 값을 삽입한 경우]

위 구조에 마지막으로 70이라는 값을 삽입해보자. 이 경우는 부모노드 분열에 대해 알아보는 것이다.

1. 값과 가장 가까운 값이 들어있는 노드를 찾는다. --> 위 구조에서 C 노드가 가장 적합하다.

2. 노드가 꽉 차 있다면 노드를 분열하여 새로운 노드를 구성한다. --> 이 과정은 30 값을 삽입 할 때 과정이므로 설명을 생략한다.

3. 만약 새로운 노드를 구성하는 도중 부모 노드가 꽉 차 있다면 부모 노드도 분열하여 새로운 노드를 구성한다.
--> 2번 과정에서 노드 분열 도중 80 값이 부모 노드에 삽입되지 못하는 상황이다. 이 때도 노드분열을 하면 되는데, 위 구조에서 보면 새로운 노드를 하나 구성하고 새로운 노드에 20, 50, 80 값 중 제일 큰 80 값을 삽입하고 나머지 값인 20, 50 값 중 제일 큰 값을 부모노드로 삽입한다. 마지막으로 남은 값은 그대로 남겨둔다.

4. 노드 분열로 인해 다른 노드가 변경되어 값들이 꽉 차 있다면 해당 값들을 비교하여 정렬한다. 


[그림 4 - 70 값을 삽입한 경우]

삽입은 위와 같은 규칙으로 계속 노드를 생성 해 나가면 된다.  


이번에는 삭제 방법에 대해서 알아보자.

[삭제]
아래와 같은 구조에 b-tree가 있다고 가정하여 하나씩 살펴보자.

[그림 5 - b-tree]

위 구조에서 50 값을 삭제하면 아래와 같이 된다.

 [그림 6 - 50 값을 삭제한 경우]

 
그럼 이번에는 위 값에서 40 값을 삭제 해보자. 과정은 아래와 같다.

1. 삭제하려는 값을 삭제한다. --> 위 구조의 경우 노드가 비어버린다.

2. 노드에 아무런 값도 없다면 부모노드에서 큰 값이 빈 노드로 내려와 노드를 채우고, 오른쪽 노드에서 작은 값이 부모노드로 올라간다. --> 위 구조의 경우 A 노드에서 70 값이 C 노드로 오게 되며, D 노드에서 작은 값인 80이 부모 노드로 가게 된다.

 
위 과정을 거치면 아래와 같아진다.

 [그림 7 - 40 값을 삭제한 경우]

이번에는 90 값을 삭제 해 보자.  

1. 삭제하려는 값을 삭제한다. --> 위 구조의 경우 노드가 비어버린다.

2. 노드에 아무런 값도 없다면 부모노드에서 큰 값이 빈 노드로 내려와 노드를 채우고, 오른쪽 노드에서 작은 값이 부모노드로 올라간다. --> 하지만 오른쪽 노드가 없다.

3. 오른쪽 노드가 없다면 빈 노드를 삭제하고, 빈 노드가 삭제된 구조에서 오른쪽 노드로 부모 노드 값 중 제일 큰 값이 내려온다. --> D 노드가 삭제되고 삭제된 구조에서 오른쪽 노드인 C 노드로 부모 노드 값 중 제일 큰 80값이 내려오게 된다.


[그림 8 - 90 값을 삭제한 경우]

삭제의 경우 노드 생성이 없기 때문에 계속 위와 같은 규칙으로 노드를 삭제 해 나가면 된다. 

'[+] Forensic' 카테고리의 다른 글

File System - NTFS (7)  (0) 2012.02.09
File System - NTFS (6)  (0) 2012.02.09
File System - NTFS (5)  (2) 2012.02.08
File System - NTFS (4)  (0) 2012.02.08
File System - NTFS (3)  (2) 2012.02.07
  1. Favicon of http://daum.net/rcdfg BlogIcon bilope 2012.04.16 07:30

    B-Tree 에 대해 공부중인 학생입니다.
    큰 도움이 되었습니다^^
    한가지 질문이있는데요,
    그림3-30에서 20과 50의 중간값인 35를 넣은경우는 어떻게돼나요?
    30과 가장 가까우니 B노드에 삽입인가요?
    아니면 부모노드에서 바로 분열하나요? 아니면 삽입될수없는값인가요?

    • Favicon of https://maj3sty.tistory.com BlogIcon MaJ3stY 2012.04.16 17:36 신고

      그림을 보면 B노드는 20보다 작은 값들이 있는 노드이고 D 노드가 20과 50 중간 값들이 있는 노드이며 C노드가 50보다 큰 값들이 있는 노드이므로 35의 경우 D노드로 삽입이 됩니다. 만약 D노드에 빈공간이 없다면 분열을 하겠죠 ^^
      도움이 되었으면 하네요~

+ Recent posts