파일처리
-
정렬 합병 #1. 대체 선택Programming/College 2010. 6. 18. 13:33
정렬되지 않은 데이터를 정렬시키면서 하나의 파일에 합병하기 위해 대체선택으로 Run을 생성해야한다. ▣ 대체선택의 런 생성 방법 1. 버퍼에 입력 파일로부터 m개의 레코드를 읽어와서 첫 번째 런을 생성한다. 2. 버퍼에서 키 값이 가장 작은 레코드를 선택하여 출력한다. 3. 입력 파일로부터 다음 레코드를 읽어와서 출력된 레코드와 대체시킨다. 이 때 만일 읽어온 키 값이 출력된 키 값보다 작으면 읽어온 키 값에 "동결(Frozen)" 표시. 동결된 레코드는 단계②에서 제외된다. 아직 동결되지 않은 레코드가 있으면 단계②로 되돌아간다. 4. 동결된 레코드들을 모두 해제하고 단계②로 돌아가 새로운 런을 생성한다. replacementSelection() // 대체선택 알고리즘 // m : 버퍼에 들어가는 레코..
-
B-트리 #4. 변수 및 함수 선언Programming/College 2010. 6. 4. 13:31
처음부터 끝까지 직접 구현해보고 싶었지만 교재의 부록으로 소스가 올려져 있었다. 그래서 열심히 베끼기!!! 물론! 이 소스가 완벽하지 않아서 개인적으로 손을 대긴했다. 그리고, 커다란 문제 발견!! 삭제 과정에서 무한 루프가 발생함. 이 부분은 이번 주말에 느긋하게 확인해보기로 하고 소스를 공개한다. #define DEGREE 5 // m차 B-트리 #define MAX_ELEMENTS 1000 // 입력되는 key의 최대 수 #define DELETE_COUNT 10 // 삭제시 빼줄 원소 수 /* global variables */ FILE* pInputStream; // input 파일의 핸들 FILE* pOutputStream; // output 파일의 핸들 typedef struct NODE {..
-
B-트리 #2. 삭제Programming/College 2010. 6. 3. 13:30
삽입 검색 알고리즘에 이어 삭제 알고리즘을 알아보자. 삭제가 수행된 B-트리가 계속 B-트리의 성질을 유지하기 위해서는 키가 삭제된 뒤에도 최소한의 키 수가 되는지를 확인해야 된다. 만일 해당 노드가 최소한으로 유지해야 될 키 수보다 작게 되는 경우에는 적절한 조치를 취해줘야 한다. 삭제를 위해서는 삽입에서와 같이 먼저 삭제하려는 키 값이 들어있는 노드를 탐색한다. 만일 삭제하려는 키 값이 내부 노드에 있다면 리프 노드에 있는 이 키 값의 후행(Successor) 키 값과 교환을 한 뒤에 리프 노드에서 삭제한다. 삭제 후 노드가 유지해야 될 최소 키 값의 수가 만족하지 않으며 재분배(Redistribution)나 합병(Merge) 방법을 이용하여 최소 키 값 수를 유지하도록 해야 한다. ▣ 재분배(Red..
-
B-트리 #1. 소개 및 검색/삽입Programming/College 2010. 6. 2. 13:30
B-트리는 인덱스를 조직하는 트리 구조로 가장 많이 사용되는 것으로써 Bayer와 McCreight에 의해 제안되었다. 이것은 m-원 균형 탐색 트리로서 효율적인 균형 알고리즘을 제공한다. 이어지는 내용에서 이해하기 쉽게 설명하기 위해 노력하겠지만 일단 위키피디아의 B-트리 링크를 제공하겠다. 위키피디아 B-트리 보기 특성 : m-원 탐색트리이다. 각 노드가 적어도 반 이상이 키 값으로 채워져 있어야 한다. 트리가 공백이 아닌 이상 처음부터 분기해야 한다. 트리가 균형을 유지해야 한다. ▣ 검색과 삽입 ◇ 검색 : B-트리의 검색은 m-원 탐색 트리의 직접 검색과 똑같은 과정을 거치게 된다. serchBT(key) // m-원 탐색 트리의 검색 알고리즘 // key : 키의 값 // x : 노드 // r..