db11 [Indexing]Bitmap Index m개의 레코드가 있으면 n개의 비트를 할당하는 방식이다. 특정한 칼럼, 예를 들면 학년(1~4)을 가지고 구분을 하면 4개의 집합으로 나뉜다. 1학년인지 파악하는 bitmap을 하나 만들 수 있다. 1학년, 3학년, 1학년, 1학년, 2학년 의 레코드가 있다고하면 10110과 같은 값을 가지게 한다. 2학년인지 파악하는 bitmap을 만들면 00001이 된다. 3학년: 01000 4학년: 00000 bitmap index는 칼럼의 값이 몇 개만 존재할 때 만들 수 있다. 위와 같은 학년이라던지 성별과 같은 칼럼에 대해서 가능하다. 학생의 학점과 같은 경우에도 가능하다. 범위에 대한 bitmap을 만들 수 있다. 4.0이상, 3.0이상 4.0 미만 과 같은 방식으로 만들 수도 있다. bitmap index.. 2020. 6. 6. [Indexing]Dynamic Hashing bucket의 수가 처음부터 고정되있지 않는 방식이다. 우리가 배울 방식은 extendable hashing이다. 리턴 값은 32bit int이어서 400만 개 정도 된다. bucket의 수를 사용하는 prefix bit수를 조절하여 결정한다. 즉, 32비트 중에 맨 앞 비트부터 몇 개를 사용할지 선택한다. bucket address table이 필요하다. 이 테이블의 크기는 hash function의 prefix에 따라 결정된다. i는 사용하는 bit 개수이다. insertion record는 key 값인 k를 가지고 있을 것이다. h(k)가 j라면 bucket j에 저장한다. bucket j가 full인 경우는 split을 한다. split 할 때 두가지 경우가 있다. 1) i > ij bucket .. 2020. 6. 6. [Indexing]Static Hashing hash table의 크기가 처음부터 고정되어 있는 것을 static hashing이라고 한다. 크기가 고정되어 있기 때문에 약점이 존재한다. hash file organization bucket: 여러 개의 record를 저장한다. bucket크기는 disk block로 사용할 수 있다. 여러 개의 버킷 중에서 버킷의 선택 기준은 hash function이 된다. record의 key 값을 hash function에 넣으면 버킷을 골라준다. 레코드를 추가할 때 뿐 아니라 search시에도 hash function을 사용한다. hash function의 input은 key 값이고 output은 bucket address이다. 다른 키여도 같은 output을 낼 수 있다. deptname이 key이고 h(.. 2020. 6. 6. [Indexing] Non-unique search key, b+ tree variation, b tree 중복된 key 값이 존재한다면 어떻게 해야할까? 이전에 simple index에서 bucket을 살펴보았다. leaf노드와 record 중간에 bucket을 두는 것을 고려할 수 있다. 아니면, 중복되는 키 값을 허용할 수도 있다. k1 2020. 6. 6. 이전 1 2 3 다음
