버킷 크기는 2이고, 모조키의 비교를 상위 비트에서 하위 비트 순서로 … | [7급 국가직 데이터베이스론] 13년 1회차 기출문제 상세 페이지
1[7급 국가직 데이터베이스론] 13년 1회차
버킷 크기는 2이고, 모조키의 비교를 상위 비트에서 하위 비트 순서로 하는 확장성 해싱(extendible hashing)으로 <사원 테이블>을 저장하려고 한다. <부서별 모조키 값>을 이용하여 부서명을 검색키로 저장할 때, 다음 설명으로 옳은 것은?
<사원 테이블>
| 사번 | 이름 | 부서명 |
|---|---|---|
| 100 | 홍길동 | 경리부 |
| 200 | 김구 | 총무부 |
| 300 | 이순신 | 인사부 |
| 400 | 안창호 | 기획부 |
| 500 | 심청 | 영업부 |
| 600 | 강감찬 | 기획부 |
| 700 | 안중근 | 경리부 |
| 부서명 | h(부서명) : 모조키 |
|---|---|
| 경리부 | 11110001 |
| 총무부 | 10100011 |
| 영업부 | 11001101 |
| 인사부 | 00110101 |
| 홍보부 | 01001101 |
| 기획부 | 10011000 |
1
사번 100과 사번 500 레코드는 같은 버킷에 저장된다.
2
사번 200의 레코드가 저장된 버킷의 지역깊이(local depth)는 2이다.
3
레코드를 저장하기 위해 모두 5개의 버킷이 생성되고, 버킷에 2개의 레코드가 저장된 버킷의 개수는 3개이다.
4
전역깊이(global depth) 값과 사번 300인 레코드가 저장된 버킷의 지역깊이 값을 더하면 4가 된다.
해설
최종 상태에서 전역깊이는 3, 사번 300 레코드가 있는 버킷의 지역깊이는 1이므로 둘을 더하면 4가 된다.
모조키 앞 비트는 경리부 1111, 총무부 1010, 인사부 0011, 기획부 1001, 영업부 1100이며, 사번 순으로 삽입한다.
사번 100·200으로 첫 버킷이 차고, 300 삽입 시 첫 비트로 분할(전역깊이 1): 0 버킷 [300], 1 버킷 [100, 200].
400 삽입 시 1 버킷이 넘쳐 두 비트로 분할(전역깊이 2): 10 버킷 [200, 400], 11 버킷 [100]. 이어 500은 11 버킷 [100, 500]에 들어간다.
600 삽입 시 10 버킷이 넘쳐 세 비트로 분할(전역깊이 3): 100 버킷 [400, 600], 101 버킷 [200].
700 삽입 시 11 버킷이 넘쳐 지역깊이 3으로 분할: 110 버킷 [500], 111 버킷 [100, 700]. 0 버킷 [300]은 지역깊이 1 그대로이다.
- 사번 100과 500이 같은 버킷이라는 설명: 세 번째 비트가 서로 달라 마지막 분할에서 다른 버킷으로 나뉜다.
- 사번 200 버킷의 지역깊이가 2라는 설명: 600 삽입 때 분할되어 지역깊이는 3이다.
- 레코드 2개가 저장된 버킷이 3개라는 설명: 버킷은 모두 5개가 맞지만 2개씩 찬 버킷은 [400, 600]과 [100, 700] 두 개뿐이다.
오류나 개정된 내용이 보이면 알려주세요