RDBMS/File Basics

선형 해싱 (Linear hashing) 선형 해싱은 next에 대한 정보가 필요 (next 이전이면 3bit 접근, 이후이면 2bit 접근) 별도로 유지하거나, 유지 안해도 bucket 개수로 evaluation 가능할 듯 확장성 해싱 (Extendiable hashing) 확장성 해싱은 global 디렉터리 구조(bucket address table)를 유지해야 한다 선형 해싱 vs 확장성 해싱 선형 해싱과 확장성 해싱을 사용해도 데이터의 이동을 완전히 피할 수는 없지만 modular 보다는 낫다. (overflow가 발생하는 버킷만 split) 확장성 해싱은 global 디렉터리 구조(bucket address table)를 유지해야 한다는 단점이 있지만, 무조건 한 번의 쿼리로 데이터를 읽어올 수..

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