RDBMS/File Basics

왜 선형 해싱과 확장성 해싱이 modular 보다 나은가? modular는 overflow로 인한 확장이 발생했을 때, 전체 데이터를 다 재배치해주어야 한다. 반면 선형 해싱과 확장성 해싱은 overflow가 발생하는 버킷만 split하므로 데이터 재배치를 최대한 줄일 수 있다. 즉 선형 해싱과 확장성 해싱을 사용해도 데이터의 이동을 완전히 피할 수는 없지만 modular 보다는 낫다. 선형 해싱 (Linear hashing) 선형 해싱은 next에 대한 정보가 필요 (next 이전이면 3bit 접근, 이후이면 2bit 접근) 별도로 유지하거나, 유지 안해도 bucket 개수로 evaluation 가능할 듯 확장성 해싱 (Extendiable hashing) 확장성 해싱은 global 디렉터리 구조(bu..

6장. 물리적 데이터베이스 설계 : 인덱스 관련 B 트리 이진트리 (binary search tree) (2-원 탐색 트리) 의 단점? 한쪽으로 편향되는 경우 탐색이 오래걸린다. 분기율(branching factor)이 2로 너무 낮아 트리가 너무 높아지고 탐색 경로가 길어질 수 있다. B 트리? B 트리의 B는 Balance로, 균형 트리다. m-원 탐색 트리로 분기율 선택 가능. 특징 leaf node 뿐만 아니라 중간 node에도 모두 데이터 레코드의 주소를 저장. 따라서 순차 탐색 하는 경우 중위 순회 해야 함. 순차 탐색 성능 나쁨. 반면 최상위 node가 가리키는 데이터 레코드는 빠르게 접근 가능. B+ 트리 즉 B트리와 B+트리의 가장 큰 차이는 B+트리는 leaf node만 데이터 레코드 ..