1. 파일 구조의 차이점 ----------------------------- 2
2. B+-트리에서의 과정 ---------------------------
3
Q1. 힙(heap) 파일
구조, 순차 파일 구조와 해시 파일 구조의 차이점을 1000자 이내로 비교 설명하시오(20점)
1) 힙 파일 구조
힙 파일 구조란 저장순서 고려 없이 파일 내 임의의 위치에 배치하는 것을 이야기합니다.
힙 파일 구조의 특징은 빈 공간에 무작위로 저장 된다는 것입니다. 그로인해 저장이 매우 빠를 수 있습니다.
하지만 특정한 순서 없이 저장된 데이터를 찾을 때는 순차적으로 모두 찾기 때문에 데이터를 검색 시에 매우
느려 사용 효율이 매우 떨어집니다.
2) 순차 파일 구조
순차 파일 구조란 탐색키를 기준으로 레코드가 정렬되어 저장되기 때문에 이진검색이 가능하여
자료의 검색이 매우 빠른 특징이 있습니다. 하지만 순서에
맞춰서 저장하기 때문에 저장 속도가 매우 느리며 매번 삽입과 삭제를 하기 위해 데이터를 계산하고 그에 맞는 데이터의 이동이 필요하기 때문에
삭제와 삽입에 비용이 많이 소모된다는 단점이 있습니다.
3) 해시 파일 구조
해시 파일 구조란 블록 주소를 해시 함수를 이용하여 계산해서 저장하는 방식입니다. 직접 파일 구조라고도 불리고 있습니다.
물리적 주소를 통해 직접 접근할 수 있기 때문에 접근 및 기록의 순서에는 제약이 없고 접근에 소용되는
시간이 빠르며, 삽입, 삭제, 갱신이 용이합니다. 하지만 레코드의 주소 변환
과정을 필요로 하여 이 과정에서의 시간이 필요합니다. 또한, 기억 공간의 효율이 저하될 수 있고 구현과정에서의 난이도가 높아 복잡합니다. 해시 파일 구조는 해시 함수의 차이에 따라 해시파일 구조의 성능차가 매우 심하여
쓰이긴 쓰이지만 실무에선 주로 순차 파일 구조가 사용됩니다.
검색 속도 측면에서는 순차 파일 구조 > 해시 파일 구조 > 힙 파일 구조 순으로
빠르고
저장 속도 측면에서는 힙 파일 구조 > 해시 파일 구조 > 순차 파일 구조 순으로
빠릅니다.
제가 실무자라면 저장되는 횟수보다 검색되거나 사용되는 횟수가 더 많을 것으로 예상되므로 순차
파일 구조를 선호할 것 같습니다.
Q2. 아래의 URL의 B+-트리 애니메이션을 참조하여 B+-트리의 구조와 B+-트리에서의 탐색키
검색, 삽입, 삭제의 과정을 1500자 이내로 설명하시오(50점)
1) B+-트리의 구조
B+-트리는 파일이 커질수록 데이터를 탐색하여
접근하는 비용이 커진다는 단점을 해소하기 위해 가장 널리 사용되는 순서 인덱스의 일종으로 트리 구조를 가지고 있습니다. 루트 노드로부터 모든
단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리 형태를 가지고 있습니다. 루트 노드 혹은 단말 노드가 아닌 중간 노드는 n 과 n/2
사이의 자식을 가지며 n은 이때 트리에서 사용되는 고정 값입니다. 맨 아래의 노드가 서로를 가리키고 있는 특징을 가지고 있습니다. n-1개의
탐색기가 존재합니다.
2) 검색
가장 먼저 트리의 루트에서 시작해서 단말 노드에 도달할 때까지 아래 방향으로 검색을 하게 됩니다.
① 찾아야 하는 값이 COM44 라면 루트 노드에는 COM34가 있다면 COM44보다 작거나 가장 큰 것 중에서 가장 작은 것을 찾습니다.
② 만약에 존재하지 않는다면 가장 오른쪽 포인터를 따라서 루트노드에서 중간 노드로
이동합니다.
③ 다시 중간노드에서 검색 값보다 작거나 가장 큰 것 중에서 가장 작은 것을 찾습니다. 만약 중간노드에 ECE 24 와 ECE 31이 있다면 COM44가 중간노드의 두 개 값보다 작기 때문에 왼쪽 포인터를 따라 왼쪽 노드로
이동합니다.
④ 이동한 왼쪽 노드에서 COM44가 있다면 COM44의 왼쪽 포인터를 따라가서
접근이 가능해집니다.
3) 삽입
노드에서 유지해야 할 포인터와 탐색키의 수 증가로 인해 노드를 분할해야 할 경우가 발생합니다.
① 만약에 COM24라는 새로운 자료를 추가 할 경우 루트노드에 COM34라는 값이 있다면 COM34보다 작으므로 왼쪽
포인터를 따라서 왼쪽 중간 노드를 따라갑니다.
② 중간노드의 값에 COM24가 없다면 가장 큰 것 중에 작은 것이 있는지 확인하고 없다면 가장 오른쪽 포인터를 따라서 내려갑니다.
③ 단말노드에 도착하고 나서 확인했을 때 COM24가 들어갈 공간이 있다면 해당 노드에 넣고 없다면 노드를 분할 해야 합니다.
④ 노드의 큰 값이 있다면 큰 값을 가지고 새로운 노드로 분할합니다. 또한 상위 중간노드에 새로운 노드로 찾아올 수 있도록 포인터를 만들어줍니다.
4) 삭제
노드에서 유지해야 할 포인터와 탐색키 값의 수 감소로 인해 병합 혹은 재분배의 경우 발생합니다.
① 만약에 COM 44라는 것을 삭제하기 위해서 루트노드에 COM34라는
값이 있다면 COM34의 값과 비교하여 큰 것 중에 작은 것인
오른쪽 포인터를 따라 오른쪽 중간노드로 이동합니다.
② COM 44는 중간노드에서 COM44보다 같거나 큰 것 중에 작은 값을 찾고 없다면 왼쪽 포인터를 따라 왼쪽
노드를 따라갑니다.
③ 만약 따라 내려온 왼쪽노드에 COM44가 있다면 삭제하고 해당되는 포인터도 같이 삭제해주면 됩니다. 하지만 COM44의 값을 삭제한 뒤 해당 노드의
값이 없다면 노드를 삭제해주는 과정을 거쳐야합니다.
④ 노드의 값이 모두 없어졌다면 오른쪽 형제노드에서 킷값을 재분배 받습니다. 또한 부모노드의 킷값 또한 업데이트를 진행합니다.
댓글 없음:
댓글 쓰기