7장인덱스된 순차화일 v 인덱스된순차화일의구조 u 인덱스된순차화일 (indexed sequential file) 은순차데이타화일 (sequential data file) 과인덱스 (index) 로구성 u 순차데이타화일 키값에따라레코드들이순차적으로정렬 레코드전체에대한순차접근을지원 u 인덱스화일 화일의레코드들에대한키값과포인터를저장 개별레코드에대한직접접근을지원 u 각화일은블록 (block) 으로구성 인덱스화일 인덱스블록 (index block) 으로구성 트리구조를형성 순차데이타화일 데이타블록 (data block) 으로구성 데이타블록들은연결리스트로논리적순서를유지 블록은순차적으로저장된키값과자유공간을포함 2
v 인덱스된순차화일의구조 3 v 인덱스된순차화일의구조 u 마스터인덱스 (master index) 인덱스트리의최상위레벨인덱스블록 u 인덱스엔트리의구성 < 최대키값, 포인터 > 포인터는해당키값을최대키값으로갖는다음레벨의인덱스블록이나데이타블록에대한주소 u 자유공간 (free space) 레코드의추가삽입을위한예비공간 화일생성시각블록에분산배치 u 키 32 에대한직접검색예 데이타블록 2를찾고블록내에서는순차탐색 4
레코드삽입 (1) u 삽입전의화일상태 5 레코드삽입 (2) u 15, 8 을삽입 ( 구조변경없이순차만유지 ) 6
레코드삽입 (3) u 17 을삽입 ( 데이타블록 1의분할 ) 7 레코드삽입 (4) u 9, 5, 6 을차례로삽입 ( 인덱스블록과데이타블록의분할 ) 8
v B + -트리 u Knuth 가제안한 B-트리의또다른변형 인덱스세트 (index set) 와순차세트 (sequence set) 로구성 순차탐색의성능향상을목적 B-트리의순차탐색을보완 u 인덱스세트 (index set) 리프이외의노드로구성 키값만저장 리프노드를접근하는경로로만이용 u 순차세트 (sequence set) 리프노드들로구성 실제모든 < 키값, 데이타레코드의주소 > 들이저장 키값의순서에따라모든레코드를순차접근하는데이용 9 3차 B + - 트리의예 10
m차 B + - 트리의특성 (1) 1 노드구조 <n, P 0, K 1, P 1, K 2, P 2,, P n-1, K n, P n > n : 키값의수, 1 n<m이다. P 0,, P n : 서브트리에대한포인터 K 1,, K n : 키값 2 루트는 0이거나 2에서 m개사이의서브트리를가짐 3 루트와리프를제외한모든내부노드는최소 m/2 개, 최대 m개의서브트리를가짐. 4 리프가아닌노드에있는키값의수는그노드의서브트리수보다하나적음. 5 모든리프노드는같은레벨 11 m차 B + -트리의특성 (2) 6 한노드안에있는키값들은오름차순으로정렬 (1 i n-1 에대해 K i <K i+1 ) 7 P i, (0 i n-1) 가지시하는서브트리에있는노드들의모든키값들은키값 K i+1 보다작거나같음 ( ) 8 P n 이지시하는서브트리에있는노드들의모든키값은키값 K n 보다큼 9 리프노드는화일레코드들의순차세트를나타내며모두링크로연결되어있음 10 리프노드의구조 <q, <K 1, A 1 >, <K 2, A 2 >,, <K< q, A q >, P next next > A i : 키값 K i 를저장하고있는레코드에대한포인터 m/2 q P next : 다음리프노드에대한링크 12
B + -트리와 B-트리의차이 u 인덱스세트와순차세트의구분이있으며구조가다름 인덱스세트는리프노드에있는키값을찾는경로로만이용 ( 키값만저장 ) 인덱스세트에있는키값은순차세트에다시나타남 순차세트는실제데이타레코드를찾는데이용 ( 키값과그키값을가진레코드에대한포인터가저장 ) 인덱스세트의노드와순차세트의노드에들어갈수있는키의개수가다름 ( 구조가다름 ) 순차세트의모든노드는링크로연결 화일레코드의순차접근이효율적 13 B + -트리에서키값의삽입 u B-트리의리프노드에삽입하는것과유사 다만노드가오버플로되어분할시중간키값 ( 분할된왼쪽노드에서제일큰키값 ) 이부모인덱스노드로올라가저장될뿐만아니라분할된노드에도저장. 분할생성된리프노드는순차세트의연결리스트에순차성이유지되도록적절히링크로연결 인덱스노드분할시에는 B- 트리와똑같은알고리즘을수행하고, 중간키값이부모노드로올라감 14
삽입예 (1) u 초기리프노드에키값 15, 69, 110 삽입 ( 인덱스세트가공백 ) u 키값 90 의삽입 ( 리프노드의분할 ) 15 삽입예 (2) u 키값 20, 120 의삽입 ( 트리구조에영향이없음 ) u 키값 40 의삽입 ( 리프노드의분할 ) 16
삽입예 (3) u 키값 125 의삽입 ( 리프노드와인덱스노드의분할, 트리의높이를증가 ) 17 B + -트리에서키값의삭제 u B-트리와유사 다만재분배 (redistribution) 나합병 (merge) 을요하지않는키값의삭제는리프노드에서만수행 인덱스세트에키값이나타나있는경우에도실제로삭제는하지않고분리자 (separator) 로이용 ( 다른키값을탐색할때분리키로이용 ) 18
삭제예 (1) u 삭제전 B + -트리 19 삭제예 (2) u 키값 43 의삭제 ( 인덱스세트의 43 은분리키로유지 ) u 키값 125 의삭제 ( 언더플로로재분배유발 ) 20
삭제예 (3) u 키값 55 의삭제 ( 언더플로로합병, 인덱스의키값도삭제 ) 21 B + -트리의성능 (B- 트리와비교 ) u 키값의직접검색 검색은항상리프노드 ( 순차세트 ) 까지내려가야만종료 검색하고자하는키값이인덱스세트에서발견되더라도리프노드까지내려가야만실제레코드의주소를알수있음 키값이인덱스세트에서발견되더라도레코드가반드시있다는것은아님 같은수의키값을가지고있는 B-트리에비해 B + - 트리는레벨이낮아질수있음 인덱스노드는레코드포인터를저장하지않으므로노드내공간이절약됨 트리레벨이낮아질수있음 u 순차검색 연결리스트를순회 B-트리에비해효율적 u B + -트리는직접처리와순차처리를모두필요로하는응용에서효율적 22
v VSAM 화일 u VSAM : Virtual Storage Access Method u B + -트리인덱스구조기법을이용하는대표적인인덱스된순차화일구성방법 u VSAM 화일의구조 제어구간 (control interval) 데이타레코드저장을위한공간단위 제어구역 (control area) 일정수의제어구간으로구성된공간단위 순차세트 (sequence set) 제어구역에대한인덱스를저장하는인덱스공간 인덱스세트 (index set) 순차세트에대한상위인덱스 다단계로구성 23 (1) VSAM 화일구조 레벨 3 인덱스세트... 레벨 2... 레벨 1 순차세트........................ 1 2 3 제어구간 4 5 6 7.... 제어구역 1 제어구역 2 제어구역 n-1 자유공간 24
제어구간 u 제어구간 (control interval) 하나이상의레코드를저장할수있는데이타블록 (data block) 으로구성 추가레코드삽입을위해자유공간 (free space) 을유지 레코드는키값에따라물리적순차로저장되고유지 제어정보 (control information) 를포함 레코드에대한제어정보와자유공간에대한제어정보 제어구간뒤쪽부터저장됨 제어구간의구조 레코드 1 레코드 2 레코드 3 레코드 4 레코드 5 자유공간 레코드 6 자유공간 레코드제어정보 자유공간제어정보 25 제어구역, 순차세트 u 제어구역 (control area) 일정수의제어구간으로구성 제어구간의오버플로를처리하기위하여제어구역내에제어구간을자유공간으로예비 화일생성시보통제어구역의마지막제어구간 u 순차세트 (sequence set) 순차블록 (sequence block) 으로구성되고하나의순차블록은하나의제어구역에 1:1로대응 순차블록의각엔트리는그제어구역에속하는제어구간과 1:1로대응 순차블록의엔트리는 < 제어구간의최대키값, 포인터 > 로구성되고키값순으로저장 제어구역에속하는제어구간들의논리적순서는순차 ( 물리적순서 ) 가아니라순차블록의엔트리순서에의해유지 순차세트내에서의순차블록들은제어구역을순차로유지할수있도록체인으로연결 순차접근이용이 26
인덱스세트 u 인덱스세트 (index set) 인덱스블록 (index block) 들로구성된 m-원탐색트리구조 인덱스블록의엔트리는 < 차하위레벨의인덱스블록의최대키값, 포인터 > 로구성 최하위레벨의인덱스블록엔트리들은각각하나의순차블록을가리킴 하나의순차블록내에서는엔트리들이키값의크기순으로저장되기때문에결과적으로화일전체가키순차로저장됨 27 (2) VSAM 화일에서의연산 u 키순차화일 (key-sequenced file) 을지원 레코드들을키값순으로저장하고유지 제어구간내에서레코드들은키값순으로물리적으로저장 제어구역에속한제어구간들의키값순서는순차세트의순차블록엔트리로유지 순차세트의순차블록순서는최하위레벨의인덱스블록으로순차를유지 화일을생성할때자유공간 (free space) 을분산배치 제어구간내에자유공간할당 제어구역내에자유제어구간을할당 u 순차접근 인덱스세트를탐색하여첫번째제어구역에대한순차세트의첫번째순차블록을식별 연결된순차세트의순차블록들을체인으로따라가며차례로모든제어구간을접근 u 직접접근 B + -트리와유사 레코드접근을위해서는인덱스세트, 순차세트, 제어구간순으로접근 28
VSAM 화일에서의레코드의삽입 u 레코드삽입 해당제어구간을식별하고레코드를삽입 삽입되는레코드의순차를유지하기위하여제어구간내레코드들을이동 u 제어구간이만원이되어레코드를삽입할자유공간이없을때는제어구간을분할 (control interval split) 제어구역내의자유제어구간으로레코드를절반이동 순차블록의엔트리들을조정하여제어구간의순서를유지 u 제어구역이만원이되어자유제어구간이없을때는제어구역을분할 (control area split) 화일의자유제어구역으로레코드절반을이동 순차세트체인을조정해서제어구역순서를유지 29 VSAM 화일에서의삽입예 (1) u 레코드삽입전의 VSAM 화일 { 인덱스세트 65 125 199 250 293 88 102 125 140 155 172 199 순차세트 55 60 65 FS 75 83 88 FS... {51 제어 53 구간 55 56 57 60 61 65 72 73 75 78 80 83 85 86 88 제어구역 1 제어구역 21 30
VSAM 화일에서의삽입예 (2) u 키가 52 인레코드가삽입된뒤의제어구역 1 55 60 65 FS 51 52 53 55 56 57 60 61 65 제어구역 1 31 VSAM 화일에서의삽입예 (3) u 키가 54 인레코드가삽입되어제어구간분할이일어난뒤의제어구역 1 52 55 60 65 51 56 61 53 52 57 65 54 60 55 제어구역 1 32
VSAM 화일에서의레코드의삭제 u 레코드삭제 해당레코드를식별하고물리적으로삭제 나머지레코드들의순차를유지하기위하여제어구간내레코드들을이동 만일제어구간의최대키값을삭제할때는이제어구간에대한순차블록엔트리의키값을조정 만일제어구역의최대키값을삭제할때는이제어구간에대한순차블록엔트리의키값뿐만아니라인덱스세트의엔트리도조정 33 v ISAM 화일 u 인덱스된순차화일을저장장치의물리적특성 ( 실린더와트랙 ) 을기반으로구현하는방법 u IBM 의 ISAM(Indexed Sequential Access Method) u 인덱스화일과데이타화일로구성 인덱스화일 (index file) 은 마스터인덱스 (master index), 실린더인덱스 (cylinder index), 트랙인덱스 (track index) 로구성 데이타화일 (data file) 은 기본데이타구역 (prime data area) 과 오버플로구역 (overflow area) 으로구성 34
(1) ISAM 화일의구조 u ISAM 화일의예 기본데이타구역은 6개의실린더로구성 실린더당 4 트랙 ( 한트랙은오버플로구역 ) 트랙당 5개의레코드수용 트랙당 40% 의자유공간 35 ISAM 화일의인덱스구조 u 트랙인덱스 (track index) 실린더내에실제데이타레코드들이저장되어있는트랙에대한인덱스 각실린더의첫번째트랙 ( 트랙 0) 에저장되어있음 각엔트리는 < 최소키값, 트랙번호 > 로구성 u 실린더인덱스 (cylinder index) 데이타가저장되어있는기본데이타구역 (prime data area) 즉실린더에대한포인터를가짐 각엔트리는 < 최대키값, 실린더번호 > 로구성 u 마스터인덱스 (master index) 최상위레벨의인덱스 각엔트리는 < 최대키값, 포인터 > 로구성 포인터는해당키값을가진실린더인덱스엔트리를가리킴 화일처리시메모리에상주 36
ISAM 화일에서의레코드삽입 (1) u 레코드검색과정을통해삽입해야될데이타트랙을결정 u 트랙에서는키값의오름차순이유지되도록레코드를삽입 u 트랙이만원인경우에는 오버플로구역 ( 트랙 ) 을사용 트랙인덱스에오버플로인덱스를추가 < 키값, 오버플로포인터 (op)> 오버플로구역에서레코드는삽입순서로저장되고체인으로키값순서를유지 오버플로레코드형식 < 레코드, 같은트랙의다음오버플로레코드에대한포인터 > 37 ISAM 화일에서의레코드삽입 (2) u 삽입전의 ISAM 화일 38
ISAM 화일에서의레코드삽입 (3) u 레코드 15 와 7을삽입 u 레코드 17 을삽입 ( 트랙 1에오버플로발생, 오버플로인덱스추가 ) 39 ISAM 화일에서의레코드삽입 (4) u 레코드 12 를삽입 ( 트랙 1에오버플로발생, 레코드체인형성 ) u 레코드추가삽입이많은경우 독립된실린더오버플로구역을예비 오버플로체인이길어져성능저하 주기적인화일재구성필요 40
ISAM 화일에서의레코드삭제 (1) u 방법 1 : 삭제할레코드를물리적으로삭제 삭제할레코드가기본데이타구역에있는경우 삭제할레코드뒤에있는레코드들을한자리씩왼쪽으로이동 필요한경우오버플로트랙의레코드를기본구역으로이동하고오버플로인덱스엔트리를조정 삭제할레코드가오버플로구역에있는경우 연결리스트를적절히조정하고체인에대한오버플로인덱스엔트리를조정 u 방법 2 : 삭제할레코드를물리적으로삭제하지않고삭제표시만함 검색시에삭제표시된레코드는생략 일정한주기로삭제표시된레코드를정리해야됨 단점 공간의낭비 불필요한오버플로레코드발생 41 v 인덱스된순차화일의설계 u 화일설계시고려사항 1 레코드의필드수와배치 2 레코드의키필드와크기 - 고정길이나가변길이레코드를모두수용할수있도록 - 화일에대한직접접근이용이한키선택 3 예상레코드추가삽입레코드수 - 일반적으로약 40% 의자유공간할당 4 주어진시스템에서의화일구현방법 42
인덱스된순차화일의구현 u 구현을위한결정요소 1 데이타블록의크기 2 인덱스블록의크기 3 초기인덱스레벨수 4 최대인덱스레벨 실제값은시스템본래의블록크기, 현재또는예상되는데이타레코드의수, 화일의용도등에따라결정 u 개별레코드에대한직접검색이주로요구되는응용 : 밀집인덱스를사용하는것이유리 u 순차검색이주로요구되는응용 : 데이타블록을크게하거나기본구역과블로킹인수를크게하는것이유리 43 인덱스설계 u 인덱스설계시가장중요한매개변수 인덱스블록의참조능력 : 인덱스분기율 (fanout) y = ë B / (V+P) û y : 인덱스분기율 B : 블록크기 V : 키값길이 P : 포인터길이 (V+P) : 인덱스엔트리크기 u 인덱스레벨 vs 인덱스분기율 인덱스분기율이크면 인덱스레벨은낮고 검색속도는빠름 44
인덱스설계예 u 레코드길이가 200 바이트인레코드 100 만개를저장하는인덱스된순차화일의설계 키길이 : 14 바이트 포인터의크기 : 6 바이트, 블록크기 : 2000 바이트 u 분석 블로킹인수 : 2000/200 = 10 필요한데이타블록에대한인덱스엔트리 : 10만개 인덱스엔트리의크기 : 14+6 = 20 인덱스블록의분기율 : 2000/20 = 100 최하위레벨 ( 레벨1) 의인덱스블록수 : 10만 /100 = 1000 레벨 2의인덱스블록수 : 1000/100 = 10 레벨 2의인덱스블록 10개는메모리에상주시키기엔너무크므로레벨 3의인덱스를만들어야함 : 1개의인덱스블록 ( 마스터인덱스 ) u 이설계에서레코드접근을하기위해서는 3번의디스크접근이필요 인덱스접근 2번 ( 마스터인덱스는메모리상주 ) + 레코드접근 1번 45 인덱스설계예 46