데이터 구조와 처리

계층적인 데이터 구조

선형적인 데이터 구조의 문제

• 선형적인 데이터 구조를 살펴보았고 많은 애플리케이션이 선형적인 데이터 구조로 충분하다.
• 데이터를 가져오고 싶을 경우에는 선형성이 문제가 된다.
• 연결 리스트의 길이가 n이라면 최대 n번 노드를 순회하면서 비교를 해야한다.

2진 트리

• 노드가 최대 2개의 다른 노드와 연결될 수 있기 때문에 이진트리라 부른다.
• 이진트리의 루트는 연결 리스트의 헤드에 해당한다.
• 간접 주소 지정을 활용하는 점에서 단일 연결 리스트의 삭제와 비슷하다.
  

2진트리 동작

8, 6, 3, 4, 9를 삽입하는 알고리즘의 동작

1. 8을 삽입하는 시점에 루트는 아무 노드도 가리키지 않으므로 새 노드를 만들고 이 노드를 가리키게 한다.
2. 루트가 가리키는 노드의 숫자 8과 6을 비교
3. 6이 8보다 작으므로 노드의 왼쪽을 본다.
4. 왼쪽 노드가 비었으므로 새 노드를 배치한다.
5. 9는 8보다 크므로 노드의 오른쪽을 본다.

위의 배치에서는 숫자가 5개 있지만 최악의 경우 3번만 비교하면 숫자를 찾을 수 있다.
따라서 최악의 경우 5번 비교를 해야하는 연결 리스트보다 성능이 좋다.
이진 트리의 알고리즘은 아래의 그림을 따르며 트리를 변경할 필요가 없으므로 노드를 가리키는 포인터를 가리키는 포인터를 만들 필요가 없다.

균형 이진트리 VS 비균형 이진트리

비균형 이진트리

• 단일 연결 리스트 처럼 보인다.
• 2진 트리의 장점을 잃는다.
• 사용하지 않는 왼쪽 트리 포인터로 인한 부가 비용을 감당해야한다.
• 깊이가 n일 경우 n번 원소를 비교해야 한다.

균형 이진트리

• 깊이가 n일 경우 log2n번 만 비교하면 된다.
• 따라서 균형을 회복하는 알고리즘을 사용한다.
• 자원을 더 사용하지만 n >> log2n이기 때문에 비용을 극복 가능하다.

대용량 저장장치

디스크

• 디스크의 기본단위 : 블록
• 연속적인 블록 : 클러스터

데이터는 사용 가능한 섹터가 있으면 위치에 관게없이 저장
운영체제의 장치 드라이버가 연속적으로 저장 된 것처럼 착각을 하게 한다.

데이터를 메모리상에서 관리할 때는 포인터를 통해 메모리를 참조하더라도 충분하다.
그러나 메모리는 일시적이므로 장기적으로 저장하기 위해 디스크를 사용
파일 이름이라는 영구적인 존재를 지정

아이노드

• 직접 블록 포인터 : 12개 존재하며 12 * 4096 = 49152바이트까지 데이터를 보관할 수 있다.
• 간접 블록 : 32bit 인덱스를 사용하며 한 블록에는 4바이트 인덱스가 1024개 존재한다. 따라서 블록당 4MiB까지 지원한다.
• 2중 간접 블록 : 4GiB 지원
• 3중 간접 블록 : 4PiB 지원
• 디렉터리 : 파일이름과 파일 데이터를 가리키는 아이노드를 연결해준다.
• 계층적 파일 시스템 : 디렉터리가 다른 디렉터리를 참조하는 구조

링크

• 아이노드의 구조는 트리처럼 보이나 실제로는 여러 아이노드가 같은 블록을 참조할 수 있으며 각 참조를 링크라고 부른다.
• 링크로 인해 같은 파일이 여러 디렉터리에 나타날 수 있고 편리하며 이를 위해 심볼릭 링크가 발명되었다.
• 심볼릭 링크를 허용하면 파일 시스템 그래프에 루프가 생겨 무한 루프를 감지하기 위한 코드가 필요하다.