Computer Science & Engineering

    이번에는 이전 글(https://shyeon.tistory.com/13)에서 만든 레코드파일을 관리하는 simple index 파일을 생성하고 생성한 simple index파일을 활용하여 이진탐색 방식을 이용해 원하는 레코드의 정보를 불러오는 기능을 구현해 보았다.

simple index파일에서의 key 값으로는 14바이트짜리 id가 사용된다 그리고 원하는 주소에 접근하기 위해서 페이지번호와 페이지에서의 레코드 번호가 주소값으로 사용된다. 그렇기 때문에 뒤에 널문자를 제외한 13바이트의 id, 페이지 번호로 4바이트, 레코드 번호로 4바이트 총 21 바이트가 simple index 파일의 하나의 레코드를 구성한다. 레코드 파일을 하나 넘겨줄 경우 record.idx라는 이름의 simple index 파일이 생성된다. 이때 생성된 레코드는 id에 대해 오름차순으로 정렬된다. 이 id는 정수형으로 정렬되기 때문에 자리수가 클 수록 큰 수로 판단된다. 레코드파일은 다음과 같은 명령어로 실행된다.

$ a.out i records.dat records.idx

이렇게 두 번째 인자로 i를 줄 경우 records.dat의 레코드파일로부터 records.idx라는 이름의 index 파일을 생성한다.

    만약 두 번째 인자로 b 옵션을 줄 경우 정렬된 index 파일로부터 원하는 키 값을 주었을 때 원하는 레코드의 정보를 출력한다. 실행할 경우 다음과 같이 나타나게 된다.

$ a.out b records.dat records.idx "9800001111111"

#reads:3

id=9800001111111

name=shyeon

age=24

addr=Seoul

phone=010-0000-0000

email=shyeon@shyeon.com

이렇게 records.idx에서 9800001111111이라는 키를 이진 탐색으로 찾는데 3번의 읽기를 했다는 의미로 #reads:3을 출력하고 records.idx에서 찾은 주소값으로 records.dat이라는 레코드파일에서 해당 레코드를 읽은 결과를 밑에 출력하게 된다. 만약 레코드가 존재하지 않는 경우 "no persons"를 출력한다.

https://github.com/Seo-sang/simple_index_record_file

이전 글에서 설명한 가변길이 레코드 방식을 실제로 구현해보았다. 레코드파일 person.c의 구조는 다음과 같다.

 - 레코드 파일

    1. 레코드 파일은 헤더 영역과 데이터 영역으로 이루어져있다.

    2. 헤더 영역에는 헤더 레코드가 존재하고 데이터 영역에는 여러 개의 데이터 페이지가 존재한다.

 - 헤더 레코드

    1. 헤더 레코드는 전체 데이터 페이지 수 4바이트, 레코드 파일에 존재하는 모든 레코드 수 4바이트, 마지막 8바이트에는 4바이트씩 삭제 레코드를 관리하기 위해 가장 최근에 삭제된 레코드의 페이지 번호와 레코드 번호를 가지고 있다.      2. 만약 삭제 레코드가 존재하지 않는다면 헤더 레코드의 마지막 8바이트의 값은 모두 -1이다.

    3. 레코드가 삭제되었을 때 헤더 레코드의 페이지 수나 모든 레코드의 수는 수정하지 않는다.

    4. 삭제 레코드는 연결리스트 방식으로 관리된다.

 - 데이터 페이지

    1. 데이터 페이지는 헤더 영역과 데이터 영역으로 나누어져있다.

    2. 헤더 영역에는 페이지에 저장된 레코드의 수, 각 레코드의 주소, 길이(offset, length)가 있으며 데이터 영역에는 실제 저장하려는 레코드가 저장된다.

    3. 레코드의 수, 주소, 길이는 각각 4바이트이며 첫 번째 레코드의 주소는 0이다.

    4. 데이터 페이지의 번호는 0부터 부여한다.

 - 레코드

    1. 레코드는 가변길이 방식으로 저장한다.

    2. 레코드의 필드는 구분자(delimiter)를 이용한다. 이때 구분자로 '#'을 사용한다. 

    3. 새로운 레코드는 파일의 마지막 페이지의 마지막 레코드 다음 위치에 저장되고 공간이 부족할 경우 데이터 페이지를 새로 할당하여 저장한다.

    4. 만약 삭제레코드에 새로운 레코드를 저장할 수 있는 경우 삭제 레코드에 저장한다. 이때 first-fit 방식을 이용한다.

    5. 삭제 레코드에 추가할 경우 연결리스트의 앞과 뒤를 연결해주어야한다.

    6. 삭제 레코드 중에 추가할 수 없는 경우 3번과 같이 추가한다.

    7. 레코드를 삭제할 경우 delete mark로 '*'를 사용하며 delete mark 뒤에 연결리스트에 사용될 다음 삭제 레코드의 페이지 번호와 레코드 번호가 4바이트씩 binary integer 형식으로 저장된다.

    8. internal fragmentation은 고려하지 않는다.

레코드는 다음과 같이 이루어져있다.

#define MAX_RECORD_SIZE	100 // including 6 delimeters
#define PAGE_SIZE		256 // 임의로 지정
#define HEADER_AREA_SIZE	(PAGE_SIZE/10)
#define DATA_AREA_SIZE	(PAGE_SIZE - HEADER_AREA_SIZE)

typedef struct _Person
{
	char id[14];		
	char name[18];		
	char age[4];		
	char addr[22];	   
	char phone[16];		
	char email[26];		
} Person;

#endif

위의 6개의 정보로 이루어진 구조체가 하나의 레코드로 저장된다.

완성된 코드는 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/variable_length_record

개발 환경은

OS Linux Ubuntu 20.04

gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

이다.