[CS] 계층적인 데이터 구조
이 글은 '한 권으로 읽는 컴퓨터 구조와 프로그래밍' 을 정리하여 작성한 글입니다.
계층적인 데이터 구조
앞에서는 선형적인 데이터 구조를 봤습니다.
이 선형적 구조는 데이터를 가져오는데 문제가 있습니다.
예를 들어, 연결 리스트의 저장된 데이터를 가져오려면, 리스트를 순회해야만 합니다.
리스트 길이가 n이라면 최대 n번 노드를 순회해야 한다는 것입니다.
앞에서 연결 리스트의 노드를 연결하기 위해서 포인터를 사용했습니다.
이 포인터 수에는 제한이 없기 때문에, 메모리 공간이 허용하는 한 원하는데로 데이터를 조작할 수 있습니다.
2진 트리
간단한 계층적 데이터 구조로 2진 트리가 있는데,
'2진' 이라는 말은 2진수가 아니라 최대 2개의 다른 노드와 연결될 수 있기 때문에 붙은 말입니다.
아래 그림에서 트리의 루트는 연결 리스트의 헤드에 해당합니다.
빙고 게임에서 불리는 숫자를 2진 트리로 저장하려고 합니다.
아래 그림은 트리에 수를 삽입하는 알고리즘 입니다.
이 알고리즘은 간접 주소 지정을 활용한다는 면에서 단일 연결 리스트의 삭제와 비슷합니다.
8, 6, 9, 4, 7을 삽입하는 것으로 알고리즘의 동작을 살펴보겠습니다.
루트가 아무 노드를 가리키고 있지 않음을 확인 -> 새 노드를 만들고 루트가 이 노드를 가리키게 함 ->
8을 루트에 삽입 -> 루트에 노드가 있음을 확인 -> 루트와 삽입할 숫자 6 비교 -> 6이 작은 것을 확인
-> 왼쪽을보고 비어 있으므로 새 노드 삽입 -> 9는 오른쪽 노드에 삽입 -> 반복
이 데이터 구조 내부에 숫자가 5개가 있지만, 최대 3번만 비교하면 원하는 숫자를 찾을 수 있습니다.
또한, 이 알고리즘에서는 트리를 변경할 필요가 없어
노드를 가리키는 포인터를 가리키는 포인터를 만들 필요가 없습니다.
트리의 노드 구성은 원소 삽입 순서에 따라 달라지는데,
아래의 그림은 단일 연결 리스트처럼 보이며,
2진 트리의 장점을 잃을 뿐만 아니라 사용하지 않는 왼쪽 트리 포인터로 인한 비용이 늘어납니다.
따라서, 아래 그림의 오른쪽과 같은 모습의 유지가 필요합니다.
2진 트리에 대상을 검색하는 연산은 트리 깊이에 의해 정의됩니다.
만약, n계층 만큼 아래로 내려가면, n번만 원소 비교를하면 됩니다.
균형 잡힌 트리는 logn번만 비교하면 됩니다.
대용량 저장장치
이번에는 디스크 드라이브를 자세하게 살펴보겠습니다.
디스크의 기본 단위는 블록이고 연속적인 블록을 클러스터라고 부릅니다.
클러스터는 한 트랙안에 연속적인 섹터로 이루어져,
데이터를 한 클러스터에만 저장할 수 있다면, 좋은 성능을 가집니다.
그러나 데이터가 너무 큰 경우가 있을 수 있고, 일반적 해법으로는 바람직하지 않은 방법입니다.
대신, 데이터는 사용 가능한 섹터가 있으면 위치와 관계없이 저장되고
운영체제의 장치 드라이버가 데이터가 연속적으로 저장된 것 같은 착각을 불러일으킵니다.
데이터를 저장하기에 위해서는 충분한 크기가 되도록
고정된 크기의 블록을 여럿 확보해서 데이터를 이런 블록에 나눠 담아야합니다.
연결 리스트 순회는 시간이 오래 걸려, 어떤 디스크 블록이 사용중인지 알아내는데 좋은 방법은 아닙니다.
데이터를 메모리상에서 관리할 때는 포인터를 통해 참조하는 것으로 충분하지만,
장기적으로 데이터를 저장하기 위해서는 디스크를 사용하므로 영구적인 존재가 필요합니다.
이러한 영구적인 해답은 파일 이름입니다.
이제 파일 이름을 디스크에 저장할 방법과 파일의 데이터가 저장된 디스크 블록을 연결할 방법이 필요합니다.
아이노드
아이노드는 디스크 블록에 대한 인덱스와 노드를 합친 단어로 위의 문제를 해결할 방법입니다.
먼저, 블록 중 일부를 아이노드로 따로 지정합니다.
아이노드에는 파일에 대한 여러가지 정보(파일 이름, 파일 소유자, 파일 크기, 파일에 대한 허가 내역) 등
여러가지 정보가 들어가 있습니다.
그리고 아이노드는 아래 그림처럼 파일 데이터가 들어가 있는 블록에 대한 인덱스도 포함됩니다.
아이노드는 보통 직접 블록 포인터(실제로는 인덱스)가 12개가 있습니다.
따라서 최대 4096 * 12 = 49152바이트 까지 데이터를 저장할 수 있습니다.
대부분은 이정도로 충분하지만, 더 커지면 간접블록을 이용합니다.
2중 간접은 4GiB(기비바이트), 3중 간접은 4PiB (페비바이트)까지 지원합니다.
아이노드 정보 중에는 블록에 데이터가 있는지 디렉터리 정보가 있는지 표시하는 것도 있습니다.
디렉터리는 파일 이름과 파일 데이터를 가리키는 아이노드를 연결합니다.
이는 디렉터리가 다른 디렉터리를 참조할 수 있고, 트리 구조의 계층적 파일 시스템이 생겼다는 것입니다.
이 시점에서는 모든 구조가 트리처럼 생각될 것입니다.
그러나 여러 아이노드가 같은 블록을 참조할 수 있습니다.
이를 링크라고 부르는데, 이로 인해 같은 파일이 여러 디렉터리에 나타날 수 있습니다.
심볼릭 링크
디렉터리에 대해 링크를 할 수 있으면 편리하다는 사실에 의해 심볼릭 링크가 발명되었습니다.
하지만 심볼릭 링크를 허용하면 그래프에 루프가 생깁니다,
이로 인한 무한 루프를 감지하기 위해 특별한 코드가 필요합니다.
이제는 사용 중인 블록에 대한 정보를 저장할 수 있는 복잡한 구조가 생겼습니다.
하지만, 아직 가용 공간을 추적하는 효율적인 방법이 없습니다.
가용 공간을 추적하는 방법으로 각 블록을 1비트로 표현하는 비트맵 방식이 있습니다.
이 방법은 비트맵이 아주 커질 수 있습니다. 8TB 디스크 드라이브를 다루기 위해 20억 비트가 필요한데
이는 256MiB의 공간입니다. 물론 전체 디스크의 0.01%보다 적은 공간을 사용하고 모든 비트맵
데이터가 항상 메모리에 있어야 할 필요는 없어 충분히 채택할만 합니다.
비트맵을 사용하면 간단하고 효율적입니다. 1이 사용중, 0이 사용 가능한 블록을 가리키면
쉽게 가용 블록을 찾을 수 있습니다.
그러나 이 접근 방법은 파일 시스템 그래프와 가용 공간을 나타내는 비트맵 사이에 동기화가 깨질 수 있습니다.
예를 들어 디스크 데이터를 기록하는 도중 전원이 꺼질 수 있습니다.
컴퓨터 전면 패널에 깜빡이는 전구와 스위치가 있던 시절에는 직접 전면 패널 스위치를
조작해 아이노드 번호를 입력함으로 파일을 수리해야 했습니다.
파일 시스템 그래프를 뒤지면서 가용 블록 데이터와 비교해주는 fsck 등의 프로그램이 개발되면서
이러한 문제가 사라졌습니다.
fsck는 더 나은 접근 방법이지만, 디스크가 커짐에 따라 시간도 늘어났습니다.
이제는 오류를 더 효율적으로 수정할 수 있도록 설계된 저널링 파일 시스템이 사용됩니다.