목차
1장 화일구조의 설계와 명세에 대한 소개 = 1
1.1 화일구조 설계의 본질 = 2
1.2 화일구조 설계의 개략 = 3
1.3 개념적 도구 : 화일구조 기호 = 5
1.4 객체지향적인 도구 : 화일구조를 유용하게 만들기 = 6
1.5 C++에서 객체 사용하기 = 6
요약 = 11
용어정리 = 11
추가적인 참고 문헌 = 13
프로그래밍 프로젝트 = 13
2장 기초적 화일 처리 연산 = 15
2.1 물리적 화일고 논리적 화일 = 16
2.2 화일 열기 = 19
2.3 화일 닫기 = 21
2.4 판독과 기록 = 22
2.4.1 판독, 기록 함수들 = 22
2.4.2 C 스트림과 C++스트림 클래스를 갖는 화일 = 23
2.4.3 화일의 내용을 표시해 주는 C++ 프로그램 = 26
2.4.4 화일 끝(end-of-file)의 탐지 = 28
2.5 탐색 = 29
2.5.1 C스트림에서의 탐색 = 30
2.5.2 C++스트림 클래스에서의 탐색 = 31
2.6 화일 안의 특수 문자들 = 32
2.7 UNIX의 디렉토리 구조 = 33
2.8 물리적 장치와 논리적 화일 = 35
2.8.1 화일로서의 물리적 장치 = 35
2.8.2 콘솔,키보드, 표준 에러 = 35
2.8.3 입출력 전환과 파이프 = 36
2.9 화일엘 관련된 해어화일들 = 37
2.10 UNIX의 화일 시스템 명령들 = 38
요약 = 39
용어정리 = 40
추가적인 참고 문헌 = 44
연습문제 = 44
프로그래밍 연습문제 = 46
프로그래밍 프로젝트 = 47
3장 보조 기억장치와 시스템 소프트웨어 = 49
3.1 디스크(Disk) = 52
3.1.1 디스크의 구성 = 52
3.1.2 필요한 공간과 용량 측정 = 55
3.1.3 섹터롤 구성된 트랙 = 57
3.1.4 블럭으로 구성된 트랙 = 62
3.1.5 디스크 정보 오버헤드(nondata overhead) = 64
3.1.6 디스크 접근에 필요한 비용 = 65
3.1.7 블럭크기기가 성능에 미치는 효과 : UNIX 예제 = 69
3.1.8 디스크로 인한 제한사항 (disk as bottleneck) = 70
3.2 자기 테이프(Magnctic Tape) = 73
3.2.1 테이프 시스템의 형태 = 73
3.2.2 고성능 테이프 시스템의 예제 = 74
3.2.3 9-트랙 테이프 상의 데이타 구성 = 75
3.2.4 요구되는 테이프 길이의 측정 = 76
3.2.5 데이타 전송 시간의 측정 = 78
3.3 디스크와 테이프의 비교 = 80
3.4 CD-ROM의 개요 = 81
3.4.1 CD-ROM의 역사 = 81
3.4.2 화일 구조상의 문제 = 83
3.5 CD-ROM의 물리적 구성 = 84
3.5.1 Pits와 Lands의 판독 = 84
3.5.2 CAV와CLV의 비교 = 85
3.5.3 주소 기법 = 87
3.5.4 섹터의 구조 = 87
3.6 CD-ROM의 장점과 단점 = 90
3.6.1 탐색 성능 = 90
3.6.2 데이타 전송률 = 90
3.6.3 저장장치 용량 = 90
3.6.4 읽기 전용 접근 = 91
3.6.5 비대칭적 기록와 판독 = 91
3.7 계층으로 본 기억장치 = 91
3.8 운영체제에 의한 화일 관리 = 92
3.8.1 화일 관리기 = 93
3.8.2 입출력 버퍼 = 95
3.8.3 입출력 프로세서와 디스크 제어기 = 96
3.9 버퍼 관리 = 98
3.9.1 버퍼에서의 병목 현상 = 98
3.9.2 버퍼링 전략 = 100
3.10 UNIX에서의 입출력 = 102
3.10.1 커널 = 103
3.10.2 화일 이름과 화일의 연결 = 107
3.10.3 보통 화일, 특수 화일, 소켓 = 108
3.10.4 블럭 입출력 = 109
3.10.5 장치 구동기 = 109
3.10.6 자기 테이프와 UNIX = 110
요약 = 112
용어정리 = 115
추가적인 참고 문헌 = 122
연습문제 = 123
4장 기초적인 화일구조 개념 = 129
4.1 필드와 레코드 구성 = 130
4.1.1 스트림 화일(stream files) = 131
4.1.2 필드 구조 = 132
4.1.3 필드의 스트림 판독 = 135
4.1.4 레코드 구조 = 137
4.1.5 길이 지시자(length indicator)를 사용하는 레코드 구조 = 140
4.1.6 문자(characters)와 수(numbers)의 혼합 : 화일 덤프의 사용 = 143
4.2 버퍼를 조작하는데 클래스 사용하기 = 146
4.2.1 구분된 텍스트 필드(deliminated Text Field)를 위한 버퍼 클래스 = 147
4.2.2 버퍼 연산을 사용한 클래스 Person의 확장 = 149
4.2.3 길이기반 필드와 고정길이 필드를 위한 클래스 버퍼 = 150
4.3 레코드 버퍼 클래스를 위한 상속의 사용 = 152
4.3.1 C++ 스트림 클래스에서의 상속 = 152
4.3.2 레코드 버퍼 객체를 위한 클래스 계층 = 153
4.4 고정길이, 고정필드 버퍼의 관리 = 158
4.5 레코드 화일을 위한 객체 지향 클래스 = 160
요약 = 162
용어정리 = 163
추가적인 참고 문헌 = 164
연습문제 = 165
프로그래밍 연습문제 = 167
프로그래밍 프로젝트 = 168
5장 레코드의 화일 관리 = 169
5.1 레코드 접근 = 170
5.1.1 레코드 키 = 170
5.1.2 순차 검색(sequential search) = 172
5.1.3 순차처리(sequential processing)를 위한 UNIX의 도구들 = 176
5.1.4 직접 접근(direct access) = 177
5.2 레코드 구조에 관한 것들 = 180
5.2.1 레코드 구조와 레코드 길이의 선택 = 180
5.2.2 헤더 레코드(header records) = 182
5.2.3 C++버퍼 클래스에 헤더를 추가하기 = 184
5.3 레코드 I/O 연산을 단일 클래스로 캡슐화(Encapsulating) = 185
5.4 화일 접근과 화일 구성 = 188
5.5 레코드 구조를 넘어서기(Beyond Record Structure) = 190
5.5.1 화일 접근을 위한 추상적인 데이타 모델 = 190
5.5.2 헤더와 자체 기술 화일(self-describing files) = 191
5.5.3 메타데이타(metadata) = 193
5.5.4 컬러 래스터 이미지(color raster image) = 196
5.5.5 하나의 화일에 여러 객체 타입을 섞어 놓기(mixing object type in one file) = 197
5.5.6 표현-독립적인 화일 접근(fepresentation-independent file access) = 200
5.5.7 확장성(extensibility) = 202
5.6 이식성(Portability)과 표준화(Standardization) = 203
5.6.1 이식성에 영향을 주는 요인들 = 203
5.6.2 이식성의 달성 = 205
요약 = 212
용어정리 = 214
추가적인 참고 문헌 = 216
연습문제 = 217
프로그래밍 연습문제 = 220
6장 성능 향상을 위한 화일 구성 = 223
6.1 데이타의 압축 = 225
6.1.1 또 다른 표기법의 사용 = 226
6.1.2 반복되는 열의 삭제 = 227
6.1.3 가변길이 코드의 대입 = 229
6.1.4 되돌릴 수 없는 압축 방식 = 230
6.1.5 UNIX에서의 압축 = 230
6.2 화일의 재생 이용(Reclaim)공간 = 231
6.2.1 레코드 삭제와 저장공간의 축약(storage compaction) = 232
6.2.2 동적인 공간 재생 이용(reclaim)을 위한 고정길이 레코드 삭제 = 233
6.2.3 가변길이 레코드의 삭제 = 238
6.2.4 저장공간 단편화(storage fragmentation) = 241
6.2.5 배치 전략(placement strategies) = 245
6.3 빠른 검색(Finding Things) : 내부 정렬(Internal sorting)과 이진 탐색(Binary search)의 소개 = 247
6.3.1 단순 필드와 레코드 화일에서의 조회 = 247
6.3.2 추측에 의한 검색 : 이진 탐색(binary search) = 248
6.3.3 이진 탐색 대 순차 탐색 = 250
6.3.4 메모리에서의 디스크 화일 정렬 = 251
6.3.5 이진 탐색과 내부 정력의 제약 = 252
6.4 키정렬(Keysorting) = 254
6.4.1 방법 설명 = 254
6.4.2 키정력의 제한 = 257
6.4.3 그 밖의 해결책 = 258
6.4.4 핀 레코드(pinned records) = 259
요약 = 261
용어정리 = 264
추가적인 참고 문헌 = 267
연습문제 = 268
프로그래밍 연습문제 = 271
프로그래밍 프로젝트 = 273
7장 인덱싱(Indexing) = 275
7.1 인덱스란 무엇인가? = 276
7.2 엔트리 순차 화일에 대한 단순 인덱스 = 277
7.3 객체 입출력에 대한 C++의 탬플릿 클래스 사용 = 282
7.4 데이타 객체의 인덱스된, 엔트리 순차와일에 대한 객체지향 지원 = 285
7.4.1 인덱스 화일을 관리하기 위해 요구되는 연산 = 285
7.4.2 TextIndexedFile 클래스 = 289
7.4.3 TextIndexedFile 클래스의 확장 = 290
7.5 메모리에 적재하기에는 너무 큰 인덱스 = 293
7.6 다중 키에 의한 접근을 제공하는 인덱싱 = 295
7.7 보조 키의 조합을 사용하는 검색 = 300
7.8 보조 인덱스 구조를 개선 : 역 리스트 = 302
7.8.1 첫 번째 해결책 = 303
7.8.2 더 좋은 해결책 : 참조 리스트의 연결 = 304
7.9 선택적 인덱스 = 308
7.10 바인딩(Binding) = 309
요약 = 311
용어정리 = 312
추가적인 참고 문헌 = 314
연습문제 = 314
프로그래밍 연습문제 = 316
프로그래밍 프로젝트 = 318
8장 공동 순차 처리와 큰 화일의 처리 = 319
8.1 공동순차 처리의 구현을 위한 객체-지향 모텔 = 321
8.1.1 두 리스트에서 이름들의 매치(match) = 322
8.1.2 두 리스트의 합병 = 327
8.1.3 공동순차 처리 모델의 요약 = 330
8.2 일반적인 원장(Ledger) 프로그램에 대한 모델의 응용 = 332
8.2.1 문제 = 332
8.2.2 원장(Iedger)프로그램에 모델의 응용 = 336
8.3 다원 합병(Multiway Merge)을 포함하기 위한 모델의 확장 = 341
8.3.1 K-원 합병 알고리즘 = 341
8.3.2 많은 수의 리스트들을 합병하기 위한 선택 트리(selection tree) = 342
8.4 메모리에서의 정렬에 대한 두 번째 통찰 = 343
8.4.1 처리와 입출력의 중첩(overlapping) : 힙정렬(heapsort) = 344
8.4.2 화일 판독시 힙(heap)의 설계 = 346
8.4.3 화일에 기록시 정렬 = 350
8.5 디스크 상에서 큰 화일들의 정렬을 위한 방법으로써의 합병(Merging) = 352
8.5.1 합병정렬(merge sort)시 얼마나 많은 시간이 걸리는가? = 354
8.5.2 10 배 큰 화일의 정렬 = 359
8.5.3 화일크기를 증가시키기 위한 비용 = 361
8.5.4 하드웨어에 기반한 향상 = 362
8.5.5 다단계 합병(multiple-step merge)을 사용한 탐색의 수 감소 = 364
8.5.6 대체 선택(replacement selection)을 사용한 분할 길이의 증가 = 368
8.5.7 대체 선택에 다단계 합병을 추가하기 = 377
8.5.8 대체 선택으로 2개의 디스크 드라이브를 사용하기 = 377
8.5.9 더 많은 수의 드라이브와 프로세서의 사용 = 380
8.5.10 멀티프로그래밍의 효과 = 380
8.5.11 외부 정렬을 위한 개념적 도구(toolkit) = 381
8.6 테이프 상에서 화일의 정렬 = 382
8.6.1 균형 합병(balanced merge) = 383
8.6.2 K-원 균형 합병 = 384
8.6.3 다중단계 합병(multiphase merges) = 385
8.6.4 외부 정렬을 위한 테이프 대 디스크 = 388
8.7 정렬-합병 패키지 = 389
8.8 UNIX에서 정렬과 공동순차 처리 = 390
8.8.1 UNIX에서의 정력과 합병 = 390
8.8.2 UNIX에서 공동순차 처리 유틸리티 = 392
요약 = 396
용어정리 = 399
추가적인 참고 문헌 = 403
연습문제 = 403
프로그래밍 연습문제 = 407
프로그래밍 프로젝트 = 407
9장 다단계 인덱싱과 B-트리 = 409
9.1 서론 : B-트리(B-tree)의 발명 = 411
9.2 문제점의 진술 = 413
9.3 이전 탐색 트리 인덱싱 = 413
9.3.1 AVL 트리 = 418
9.3.2 페이지화된 이진 트리(paged binary trees) = 421
9.3.3 페이지화된 트리가 가지는 문제점 = 423
9.4 단단계 인덱싱 : 트리 인덱스의 보다 나은 접근 방법 = 427
9.5 B-트리 : 상향식 작업 = 429
9.6 B-트리 생성의 예 = 430
9.7 B-트리의 객체지향표현 = 434
9.7.1 클래스 BTreeNode : 메모리에 B-트리 노드를 표현하기 = 434
9.7.2 클래스 BTree : B-트리 노드의 화일 지원하기 = 436
9.8 B-트리 메소드 검색, 삽입, 그 밖의 것 = 436
9.8.1 검색 = 436
9.8.2 삽입 = 439
9.8.3 생성, 열기, 닫기 = 442
9.8.4 B-트리를 검사하기 = 442
9.9 B-트리 용어 유래 = 443
9.10 B-트리 성질의 형식적 정의 = 445
9.11 최악 경우 검색 깊이(Worst-Case Search Depth) = 446
9.12 삭제(Deletion), 합병(Merging), 재분배(Redistribution) = 447
9.12.1 재분배 = 451
9.13 삽입시의 재분배 : 저장공간 효율을 개선시키는 방법 = 452
9.14 B-트리 = 453
9.15 페이지의 버퍼링 : 가상 B-트리 = 454
9.15.1 LRU교체 = 455
9.15.2 페이지 높이에 근거한 교체 = 456
9.15.3 가상 B-트리의 중요성 = 457
9.16 가변길이 레코드와 키 = 457
요약 = 459
용어정리 = 460
추가적인 참고 문헌 = 462
연습문제 = 464
프로그래밍 연습문제 = 467
프로그래밍 프로젝트 = 467
10장 인덱스 순차 화일 접근 및 전위 B^+ 트리 = 469
10.1 인덱스 순차 접근 = 470
10.2 순차 집합의 유지 = 471
10.2.1 블럭들의 이용 = 472
10.2.2 블럭 크기의 선택 = 475
10.3 순차 집합에 단순 인덱스의 삽입 = 476
10.4 인덱스의 내용 : 키 대신 분리자 이용 = 479
10.5 단순 전위 B^+트리 = 481
10.6 단순 전위 B^+트리 유지 = 482
10.6.1 순차 집합에서 한 블럭의 지역화된 변화 = 482
10.6.2 인덱스 집합에서 여러 개의 블럭을 수반하는 변화 = 484
10.7 인덱스 집합 블럭의 크기 = 487
10.8 인덱스 집합 블럭들의 내부 구조 : 가변적 차수를 가지는 B-트리 = 488
10.9 단순 전위 B^+ 트리의 적재 = 492
10.10 B^+트리 = 496
10.11 B-트리, B^+트리, 단순 전위 B^+ 트리의 관점 차이 = 498
요약 = 502
용어정리 = 504
추가적인 참고 문헌 = 506
연습문제 = 506
프로그래밍 연습문제 = 510
프로그래밍 프로젝트 = 511
11장 해싱(Hashing) = 513
11.1 소개 = 515
11.1.1 해싱이란? = 515
11.1.2 충돌(collision) = 516
11.2 간단한 해싱 알고리즘 = 519
11.3 헤싱 함수와 레코드 분포 = 522
11.3.1 레코드 주소의 분표 = 522
11.3.2 그 밖의 해싱 방법 = 524
11.3.3 레코드 분포의 예측 = 525
11.3.4 채워진 화일의 충돌 발생 횟수 예측 = 530
11.4 추가적인 메모리 사용 = 531
11.4.1 패킹밀도(packing density) = 532
11.4.2 패킹밀도에 따른 충돌 횟수 예측 = 532
11.5 선형 조사방법에 의한 충돌 해결 = 536
11.5.1 선형 조사 방법 = 536
11.5.2 탐색 길이(search length) = 538
11.6 동일 주소에 여러 레코드 저장 : 버킷 = 541
11.6.1 버킷이 성능에 미치는 영향 = 543
11.6.2 구현에 관련된 문제 = 547
11.7 삭제 = 550
11.7.1 삭제 처리를 위한 삭제표시 = 550
11.7.2 삭제표시와 삽입 연산의 관계 = 552
11.7.3 삭제와 삽입이 성능에 미치는 영향 = 553
11.8 다른 충돌 해결 기법 = 553
11.8.1 이중 해싱 (double hashing) = 554
11.8.2 체인으로 연결된 선형 조사방법(chained progressive overfiow) = 554
11.8.3 별도의 오버플로우 영역을 체인으로 연결하기 = 557
11.8.4 산재테이블(scatter tables) = 558
11.9 레코드 접근의 패턴 = 559
요약 = 561
용어정리 = 564
추가적인 참고 문헌 = 567
연습문제 = 568
프로그래밍 연습문제 = 573
12장 확장성 해싱(Extendible Hashing) = 575
12.1 서론 = 577
12.2 확장성 해싱 방법 = 578
12.2.1 트라이(tries) = 578
12.2.2 트라이를 디렉토리로 변환 = 579
12.2.3 오버프로우 처리 : 분할(splitting) = 580
12.3 구현 = 583
12.3.1 주소 생성 = 583
12.3.2 버킷과 디렉토리를 표현하는 클래스 = 585
12.3.3 버킷과 디렉토리 연산 = 590
12.3.4 구현 요약 = 595
12.4 삭제 = 596
12.4.1 삭제 과정의 개요 = 596
12.4.2 버디 버킷을 찾는 절차 = 597
12.4.3 디렉토리의 축소(collapsing) = 598
12.4.4 삭제 연산의 구현 = 599
12.4.5 삭제 연산의 요약 = 601
12.5 확장성 해싱의 성능 = 602
12.5.1 버킷 공간 이용률 = 602
12.5.2 디렉토리 공간 이용률 = 603
12.6 다른 접근방식들 = 604
12.6.1 동적 해싱(dynamic hashing) = 604
12.6.2 선형 해싱(linear hashing) = 606
12.6.3 제어된 분할(controlld splitting)접근방법 = 609
요약 = 611
용어정리 = 612
추가적인 참고 문헌 = 614
연습문제 = 615
프로그래밍 연습문제 = 617
프로그래밍 프로젝트 = 617
부록 A CD-ROM화일 = 619
부록 B ASCII 테이블 = 633
부록 C C++스트림 클래스를 사용한 형식화된 출력 = 635
부록 D 단순 화일 입력/출력 예제 = 639
부록 E Classes for Buffer Maniqulation = 647
부록 F A Class Hierarchy for Buffer Input/Output = 667
부록 G 키에 의한 레코드의 단일(Single)단계 인덱싱 = 705
부록 H 공동 순차 처리 = 729
부록 I B-Trees를 이용한 다단계 인덱싱 = 751
부록 J 확장성 해싱 = 765
참고문헌 = 781
찾아보기(한글) = 787
찾아보기(영문 : 약어 및 저자) = 801
