B+Tree프로그램 설치 및 운용 Database Laboratory

Presentation on theme: "B+Tree프로그램 설치 및 운용 Database Laboratory"— Presentation transcript:

1 B+Tree프로그램 설치 및 운용 Database Laboratory

2 차 례 B+Tree 의 개념 B+Tree를 구성하기 위한 프로그램 실행 키값과 파일 포인터 추출

3 B+Tree 데이터의 삽입과 삭제에도 불구하고 효율성을 유지 하는 인덱스 구조들 중에서 가장 널리 사용되는 구조
B+Tree 는 균형트리(Balance Tree) 형태 데이터의 삽입과 삭제에도 불구하고 효율성을 유지하는 인덱스 구조들 중에서 가장 널리 사용되는 구조로서 B+Tree 는 균형트리(Balance Tree) 형태입니다.

4 B+Tree 구성을 위한 프로그램 파일 포인터 추출 프로그램 B+Tree 프로그램 Btree.c Bplus.tar.gz
자세한 설명은 다음 페이지 부터 자세히 설명하겠습니다.

5 파일 포인터 추출을 위한 준비사항 다운 받은 프로그램의 압축을 풉니다. 준비사항 B+ tree를 실행 전에 준비사항들
샘플 데이터 파일 -> sample.dat 파일 포인터 추출 프로그램 -> Btree.c B+ tree를 실행 전에 준비사항들 center에 자신의 계정으로 접속한다.(SSH Secure Shell Client를 사용하여 접근). 아이피: 아이디 : 학번 비번 : 학번 위의 프로그램은 리눅스 홈페이지에서 다운 받으시면 됩 니다. $ cp ../bplustree.zip . 다운 받은 프로그램의 압축을 풉니다. unzip bplustree.zip 데이터의 파일 포인터를 추출하기 위한 준비 사항으로, Sample.dat 와 btree.c 파일을 사이버 강의 사이트로 부터 다운 받아, 자신의 센터 계정에 업로드합니다. 다음에는 정렬된 인덱스 파일을 가지는 B+Tree 인덱스를 구성하는 방법을 실습합니다.

6 샘플 데이터 파일 필드 구성 UNIX SORT : sort –k 2,2 original_file > sorted_file
First Name Last Name city_code county mail_zip Telephone 위의 샘플 데이터 파일을 Last Name 을 기준으로 정렬합니다. 정렬하는 방법은 Excel 에서 하는 방법과 UNIX에서 하는 방법 등 많은 방법이 있습니다. UNIX SORT : sort –k 2,2 original_file > sorted_file 샘플 데이터 파일은 위와 같이 총 6개의 필드로 구성되어 있습니다. 샘플 데이터 파일은 2번째 열인 last name을 기준으로 정렬합니다. 정렬방법은 excel 에서 하는 방법과, 유닉스 그리고 기타 많은 방법이 있습니다. 유닉스에서 하는 방법을 소개하면, 정렬 명령어 sort 와 기준열을 지정하는 옵션인, -k 그리고 정렬기준이 되는 2 번째 열을 정하고, 지정한 후 정렬되어야 하는 파일 이름을 지정하고 꺽쇠 표시한 후 정렬한 후의 파일 이름을 지정합니다. 그 실행 예는 다음 페이지에서 보이겠습니다.

7 데이터 정렬 예 정렬 실행 정렬 결과 정렬실행과 정렬된 데이터를 보이고 있습니다. 각각의 파일포인터를 추출합니다.

8 파일 포인터 추출 데이터 정렬을 마쳤으면 키에 대한 파일 포인터를 추출 합니다. 파일 포인터를 추출하는 프로그램
Btree.c 사용법은 다음과 같습니다. 컴파일 방법 데이터 파일을 정렬한 후, b+tree에 삽입을 위한 파일포인터를 추출해야 합니다. 파일포인터 추출프로그램은 btree.c 입니다. 프로그램을 컴파일 하는 방법은 다음과 같습니다. gcc –o Btree_pointer Btree.c 로 실행파일 이름을 btree-pointer 로 지정합니다. -o 옵션은 실행 파일 명을 정하는 옵션입니다.

9 파일포인터 추출프로그램 실행 사용법 Btree_pointer [original_file] [point_value_file] [data_num] 실행 예 실행명령어와 정렬된 파일명(sample.sorted) 그리고 추출된 포인터 값이 저장되어 있을 파일명을(ponint.dat) 쓴 후 전체 데이터의 개수를 씁니다. Sample 데이터의 개수는 7567개 입니다. ./Btree_pointer sample.sorted point.dat 7567

10 파일 포인터 추출프로그램 설명 <Btree.c> FILE *inFP,*outFP;
main (int argc, char *argv[]) { char first_name[50]; char last_name[50]; char prim_city[50]; char county[50]; char mail_zip[50]; char phone[50]; 원본 파일을 가리키는 inFP와 추출된 파일 포인터 값을 저장할 outFP 를 선언하고, 데이터 파일이 총 6개의 열로 구성되어 있기 때문에 firt_name, last_name, prim_city, county, mail_zip, phone 6개의 변수를 선언합니다.

11 Cont’s inFP = fopen(argv[1], "r"); //원본 데이터파일값 입력
outFP = fopen(argv[2],"w"); // 결과 파일명 numLeaf = (int) atoi(argv[3]); // 데이터 개수를 입력(데이터 개수는 7567개) strcpy(prev_key,"-1"); inFP 에 원본 데이터파일값을 입력하고, outFP에 결과파일명, 그리고 numLeaf 에 데이터 개수를 입력합니다. Prev_key 변수에 -1을 저장합니다.

12 Cont’ while (line_no < numLeaf) { //전체 데이터 개수 만큼 루프
cLoc = ftell(inFP); //cLoc 변수에 원본 데이터 파일의 파일 포인터를 저장 if (cLoc != (int) cLoc) { printf("Error\n"); exit(10); } fscanf(inFP,"%s %s %s %s %s %s" ,first_name , last_name, prim_city, county, mail_zip, phone); //fscanf를 통해 6개의 데이터를 읽은 후, 키가 되는 last_name을 key 변수에 저장 strcpy(key,last_name); //이전 키에 저장되어 있는 키 값과 현재 키 값이 다를 경우 파일에 key 와 파일포인터를 출력 if( strcmp(key,prev_key) ){ fprintf(outFP, "%s %ld\n",key,cLoc); strcpy(prev_key,key); //이전 키 값에 현재 키 값을 입력 line_no++; if (line_no % 1000 == 0) fprintf(stdout, "processed %d lines\n", line_no); 전체 데이터 개수만큼 루프를 반복하며, 우선 cloc 변수에 원본데이터 파일의 파일 포인터를 저장합니다. Fscanf 로 6개의 데이터를 읽을 후, 키가 되는 2번째 열의 값인 last-name을 key 변수에 저장합니다. 만약 이전 키값이 저장되어 있는 prev_key와 현재 키 값인 key의 값이 다를 경우 결과 파일에 key 와 파일포인터 값을 출력합니다. 그리고 이전 키 값에 현재 키 값을 입력합니다.

13 파일 포인터 추출결과 키 , 파일포인터 파일포인터를 추출한 결과 입니다.

14 B+Tree 실습 준비사항 다음 페이지에서 B+Tree를 설치, 실행
키 값을 기준으로 정렬된 파일 -> sample.sorted 키 값과 파일포인터가 추출된 파일 -> point.dat B+Tree 프로그램 -> bplus.tar.gz Cont 프로그램 -> btreerpt_mod.c 다음 페이지에서 B+Tree를 설치, 실행 다음은 B+Tree 프로그램을 설치하고, 데이터 삽입과, 검색을 실습해 보겠습니다. B+Tree 실습에 준비사항으로 키값을 기준으로 정렬된 파일과, 키 값과 파일포인터가 추출된 파일 , B+Tree 프로그램이 필요합니다. 다음페이지 부터 B+Tree를 설치하고 실행하는 것을 실습하겠습니다.

15 B+Tree 설치 B+ tree 프로그램 실행 따라하기 mkdir db
자신의 계정 폴더 아래 bplus.tar.gz 압축파일을 db 폴더 로 복사 cp ./bplus.tar.gz ./db cd db 압축해제 명령 -> tar zxvf bplus.tar.gz 자신의 센터계정으로 접속하여 우선 새로운 폴더를 생성합니다. 생성한 폴더에 사이버 강의 게시판에서 다운받은 bplus.tar.gz 파일의 압축을 해제합니다.

16 B+Tree 준비 준비사항 b+tree 폴더 안에 복사할 파일 cp ../../sample.sorted .
cp ../../point.dat . cp ../../btreerpt_mod.c . 다음은 B+Tree 프로그램을 설치하고, 데이터 삽입과, 검색을 실습해 보겠습니다. B+Tree 실습에 준비사항으로 키값을 기준으로 정렬된 파일과, 키 값과 파일포인터가 추출된 파일 , B+Tree 프로그램이 필요합니다. 다음페이지 부터 B+Tree를 설치하고 실행하는 것을 실습하겠습니다.

17 프로그램 실행 Cont’ ⇒ btreerpt_mod.c 를 vi Editor로 다음과 같이 수정하여 저장한다.
vi btreerpt_mod.c #include<stdio.h> #include<ctype.h> #include<sys/types.h> #include<sys/file.h> #include“btree.h" #include"btconf.h“ #include"btintern.h" ⇒ #include"btlib/btree.h“ #include"btlib/btconf.h“ #include"btlib/btintern.h" 압축을 해제한 폴더에 이전에 다운받은 btreerpt.c 와 makefile을 위치시키고, Btreerpt.c 파일을 열어 다음과 같이 수정합니다. 헤더파일 3개가 위치한 디렉토리 경로를 설정하는 것입니다.

18 프로그램 실행 Cont’ gcc -I. -c -o ./btreerpt_mod.o btreerpt_mod.c
gcc -I. -o ./btreerpt_mod ./btreerpt_mod.o ./libbtree.a I(대문자 i) Btreerpt_mod.c 파일을 다음과 같이 컴파일 합니다. Gcc 명령어의 옵션인 –I옵션은 추가 헤더파일이 있는 디렉토리를 지정하는 옵션이고 –c옵션은 링킹과정을 진행하지않고 –o파일인 오브젝트 파일까지만 생성하는 옵션입니다. Libbtree.a 라는 라이브러리로 실행하여 컴파일한다는 것입니다.

19 프로그램 실행 Cont’ 명령 프롬프트에서 btreerpt_mod 명령을 실행
생성할 B+Tree Index 파일이름을 입력한다. 명령 프롬프트에서 btreerpt_mod 명령을 실행 생성할 B+Tree Index 파일이름을 입력한다. 인덱스 이름을 test.idx 를 입력한다.

20 인덱스 열기 1번 메뉴를 선택하여 인덱스를 연다 1번 메뉴를 선택하여 인덱스를 오픈합니다.

21 데이터 삽입 3번 메뉴를 선택해서 키와, 파일포인터를 삽입 키와 파일포인터가 저장되어 있는 파일명을 입력한다.
키와 파일포인터가 저장되어 있는 파일명인 point.dat 를 입력합니다. 삽입된 결과는 6번 Index Display 메뉴를 선택하면 확인 할 수 있습니다.

22 데이터 검색 4번 메뉴를 선택해서 데이터를 검색 정렬된 데이터 파일명을 입력한다. - > sample.sorted
찾고자 하는 키 값으로 AKIN 을 입력 4번 메뉴를 선택하여 데이터를 검색합니다 우선 데이터 파일명을 입력합니다. 파일명은 sample.sorted 입니다. 찾고자 하는 값으로 ABRAMS 를 입력합니다. 검색 결과는 화면에 디스플레이 되고, Result.dat 파일에 저장됩니다.

23 소스코드 <proc_Insert>
void proc_Insert() //B트리에서 키와 파일포인터를 입력하기 위한 함수 { FILE *FP; off_t addr; //파일을 읽기 위한 File 변수, 파일포인터를 저장할 변수인 addr char key[100]; char data_file[10]; int len; // key값을 저장할 변수, 읽을 파일의 이름,키의 길이 변수 printf("Input insert data file name :"); //B트리 메뉴에서 3번 입력시 나오는 출력 문 scanf("%s",data_file); FP = fopen(data_file,"r"); //scanf로 읽은 파일을 open //파일의 마지막까지 루프가 실행되며, key 값과 해당 파일포인터, 즉 주소값을 읽음 while(fscanf(FP,"%s %d",key,&addr) != EOF) { len = strlen(key); //bt_insert 함수를 이용 index, 키와, 키의 길이, 주소를 리턴 if (bt_insert(globf, key, len, addr, 0) == BT_ERR) { bt_perror(globf, "error in insert"); return; } printf("\n"); fclose(FP); B+Tree 에 키와 파일포인터를 입력하기 위하여 사용되는 함수입니다. 키와 파일포인터를 저장하고 있는 파일을 읽기 위한 FP 와, 파일포인터를 저장할 변수인 addr, 그리고 키 값을 저장할 변수 key를 선언합니다. data_file과 len 은 읽을 파일의 이름과, 키의 길이를 저장하는 변수입니다. 우선 키와 파일 포인터값을 가지고 있는 파일의 이름을 입력하면, data_file 변수에 저장됩니다. 파일이 마지막이 아닐때 까지 루프가 실행되며, key 값과 해당 파일포인터 즉, 주소값을 읽습니다. 키의 길이를 계산한 후, bt_insert() 함수를 이용하여 키와, 주소를 저장하게 됩니다. 여기서 globf는 b+tree index 노드이고, key, 키의 길이, 해당 주소값 총 4개의 파라미터를 넘기게 됩니다. 만약 삽입에 실패할 경우 BT_ERR 메시지를 반환 받고 삽입은 중지 됩니다. bt_insert() 함수에 대해서는 다음시간에 자세히 설명하겠습니다.

24 소스코드 <proc_search>
void proc_Search() { //데이터 검색하는 함수로, 데이터 파일을 구성하는 변수 선언, 각 변수를 선언 후 bt_find() 함수를 이용하여 검색 char key[100]; int len; off_t rrnval; char first_name[50], last_name[50], prim_city[50], county[50], mail_zip[50], phone[50],data_file[10]; FILE *data,*result; printf("Input Data file name : "); scanf("%s",data_file); data = fopen(data_file,"r"); result = fopen("result.dat","w"); printf("찾고자 하는 키값을 입력하세요.(data type is string)\n"); scanf("%s", key); len = strlen(key); 다음은 데이터 검색하는 함수인 proc_Search() 를 설명하겠습니다. 데이터 파일을 구성하는 6개 열에 대한 변수를 선언하고, 데이터 파일과, 결과 파일을 입출력 할 변수 data와 result 를 선언합니다. 찾고자하는 키 값을 입력하여 key 변수에 저장하고, Bt_find() 함수를 이용하여 검색을 합니다. 인덱스 노드와, 키값, 길이, 그리고 rrnval를 넘기면 성공적으로 검색 하였을 경우 rrnval 변수에 해당 키값의 파일포인터가 저장됩니다. Fseek 명령어로 해당 위치로 이동한 다음, 검색 기준값이 last name이고, last name으로 정렬이 되어 있기 때문에, 사용자가 검색을 원하는 key 값과, last name 이 다를 때 까지 검색을 수행합니다. 검색된 결과는 화면에 디스플레이 하고, result.dat 파일에 출력됩니다. Bt_find() 함수에 대해서는 다음 시간에 검색 슈도코드를 이용하여 자세히 설명하겠습니다.

25 소스코드 <proc_search>
// 인덱스 노드, 키값, 길이, 해당 키값의 파일포인터 if( bt_find(globf, key, len, &rrnval) == BT_OK ){ fseek(data,rrnval,SEEK_SET); //검색 기준값이 last name이고, last name으로 정렬되어 있으므로, 사용자가 검색을 원하는 key 값과, last name이 다를때 까지 검색 while(1){ fscanf(data,"%s %s %s %s %s %s",first_name,last_name,prim_city, county, mail_zip, phone); if(strcmp(key,last_name)) break; printf(“%s %s %s %s %s %s\n”,firts_name, last_name, prim_city, county, mail_zip, phone); fprintf(result,"%s %s %s %s %s %s\n",first_name,last_name,prim_city, county, mail_zip, phone); } printf("\n"); fclose(data); fclose(result); 인덱스 노드와, 키값, 길이, 그리고 rrnval를 넘기면 성공적으로 검색 하였을 경우 rrnval 변수에 해당 키값의 파일포인터가 저장됩니다. Fseek 명령어로 해당 위치로 이동한 다음, 검색 기준값이 last name이고, last name으로 정렬이 되어 있기 때문에, 사용자가 검색을 원하는 key 값과, last name 이 다를 때 까지 검색을 수행합니다. 검색된 결과는 화면에 디스플레이 하고, result.dat 파일에 출력됩니다.

26 요 약 이번 시간에는 B+Tree에 대한 개념과 유닉스 플랫폼 에서 동작하는 B+Tree 프로그램을 실행해 보았습니 다.

27 Report 여러분은 개별적으로 데이터를 구하여, 데이터의 키와 파 일포인터를 추출하고, 그것을 이용하여 B+Tree를 구성한 다음, 삽입, 검색하는 프로그램을 작성하십시오. 여러분이 사용한 데이터와 프로그램, 그리고 삽입, 검색 하는 과정을 메뉴얼 형식으로 자세히 작성하고, 사용된 파일(데이터파일, 키와 파일포인터 추출파일, B+Tree 삽 입, 검색 프로그램)에 대한 보고서를 제출

28 Report Btree 프로그램에서 btlib/bt_insert() 함수가 넘겨받은 파 라미터 5개와 bt_insert() 함수에서 사용된 함수에 대하여 조사하고 각 함수를 설명한 다음 레포트로 제출 파일의 위치는: b+tree 폴더 안에 btlib 폴더안에 btinsert.c 파 일을 참고! 5개의 파라미터(b ,key, len, rrn, dupflg) 과제 제출은 메일 제출 형식 : [데이터베이스01or02분반]학번_이름_btree실습과제 이 형식이 아닐 경우 감점! 메일 주소 : ecampus.hallym.ac.kr 제출 : 12월 9일 저녁 23:59시 까지