NTFS에서는 앞 글에서도 언급 했듯이 b-tree 를 사용한다고 했었다.
NTFS는 많은 상황에서 인덱스 구조체를 사용한다. NTFS 인덱스는 정렬된 순서로 저장된 속성들의 모음을 일컫는다.
인덱스가 제일 흔하게 사용되는 것이 디렉토리인데, $FILE_NAME 속성을 포함하기 때문이다.
NTFS에서 인덱스는 이진트리, b-tree로 정렬된다. 이진트리는 자료구조론에서 자주 언급되는 개념 중 하나이기 때문에 여기서 언급은 생략하고 b-tree에 대해서만 설명 하겠다.
b-tree는 이진트리와 유사한 형태이지만, 노드 별로 자식 노드가 2개 이상이다.
b-tree에는 여러 종류와 규칙이 있지만 여기서는 b-tree에 대해서만 설명 할 것이며 노드 삽입, 삭제에 대해서 이야기 해보도록 하겠다.
b-tree는 기본적으로 아래와 같이 생겼다.
가칭으로 각 노드에 알파벳 이름을 붙여 놨다. 이제 위 기본 구조를 이용해 삽입, 삭제를 알아보도록 하겠다.
이번에는 30이란 값을 삽입해보자. 이번의 경우는 노드가 값으로 꽉 차있을 경우 어떻게 삽입이 되는지를 알아 보는 것이다.
삽입 과정은 아래와 같다.
1. 값과 가장 가까운 값이 들어있는 노드를 찾는다. --> 위 구조에서 B 노드가 가장 적합하다.
2. 노드에 빈공간이 없을 경우 해당 노드를 분열 하여 새로운 노드를 구성한다. --> 노드를 분열한 후 노드에 들어갈 후보 값(10, 20, 30) 중 제일 큰 값을 새로운 노드로 삽입하고, 남은 두 값(10, 20) 값 중 큰 값을 부모 노드로 삽입한다. 마지막으로 남은 값(10)은 원래 노드에 남겨둔다.
3. 노드 분열로 인해 다른 노드가 변경되어 값들이 꽉 차 있다면 해당 값들을 비교하여 정렬한다.
아래는 결과물이다.
위 구조에 마지막으로 70이라는 값을 삽입해보자. 이 경우는 부모노드 분열에 대해 알아보는 것이다.
1. 값과 가장 가까운 값이 들어있는 노드를 찾는다. --> 위 구조에서 C 노드가 가장 적합하다.
2. 노드가 꽉 차 있다면 노드를 분열하여 새로운 노드를 구성한다. --> 이 과정은 30 값을 삽입 할 때 과정이므로 설명을 생략한다.
3. 만약 새로운 노드를 구성하는 도중 부모 노드가 꽉 차 있다면 부모 노드도 분열하여 새로운 노드를 구성한다.
--> 2번 과정에서 노드 분열 도중 80 값이 부모 노드에 삽입되지 못하는 상황이다. 이 때도 노드분열을 하면 되는데, 위 구조에서 보면 새로운 노드를 하나 구성하고 새로운 노드에 20, 50, 80 값 중 제일 큰 80 값을 삽입하고 나머지 값인 20, 50 값 중 제일 큰 값을 부모노드로 삽입한다. 마지막으로 남은 값은 그대로 남겨둔다.
4. 노드 분열로 인해 다른 노드가 변경되어 값들이 꽉 차 있다면 해당 값들을 비교하여 정렬한다.
이번에는 삭제 방법에 대해서 알아보자.
위 구조에서 50 값을 삭제하면 아래와 같이 된다.
그럼 이번에는 위 값에서 40 값을 삭제 해보자. 과정은 아래와 같다.
1. 삭제하려는 값을 삭제한다. --> 위 구조의 경우 노드가 비어버린다.
2. 노드에 아무런 값도 없다면 부모노드에서 큰 값이 빈 노드로 내려와 노드를 채우고, 오른쪽 노드에서 작은 값이 부모노드로 올라간다. --> 위 구조의 경우 A 노드에서 70 값이 C 노드로 오게 되며, D 노드에서 작은 값인 80이 부모 노드로 가게 된다.
위 과정을 거치면 아래와 같아진다.
이번에는 90 값을 삭제 해 보자.
1. 삭제하려는 값을 삭제한다. --> 위 구조의 경우 노드가 비어버린다.
2. 노드에 아무런 값도 없다면 부모노드에서 큰 값이 빈 노드로 내려와 노드를 채우고, 오른쪽 노드에서 작은 값이 부모노드로 올라간다. --> 하지만 오른쪽 노드가 없다.
3. 오른쪽 노드가 없다면 빈 노드를 삭제하고, 빈 노드가 삭제된 구조에서 오른쪽 노드로 부모 노드 값 중 제일 큰 값이 내려온다. --> D 노드가 삭제되고 삭제된 구조에서 오른쪽 노드인 C 노드로 부모 노드 값 중 제일 큰 80값이 내려오게 된다.
삭제의 경우 노드 생성이 없기 때문에 계속 위와 같은 규칙으로 노드를 삭제 해 나가면 된다.
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 (4) (0) | 2012.02.08 |
File System - NTFS (3) (2) | 2012.02.07 |