[데이터베이스] Ch 14. Indexing(2) - ch24. 내용 추가 : Hashing, Spatio-temporal Indexing
Reference
1. Database System Concepts-Abraham Silberschatz, Henry Korth, S. Sudarshan
2. Database System class by Professor Yon Dohn Chung, Department of Computer Science and Engineering, Korea University
24.5 Hash Indices
Static Hashing
- bucket : entries들을 저장하는 storage unit
- hash function을 이용한 search-key값을 통해 entry의 bucket을 얻는다.
- hash function, h가 search-key set K를 bucket address set B로 변환시킨다.
- In a hash index → bucket이 pointer를 저장
- In a hash file-organization → bucket이 record를 저장
Handling of Bucket Overflows
hash 함수를 아무리 잘 만들었더라도 Bucket overflow가 발생할 수 있습니다.
bucket overflow 원인
- 충분치 않은 bucket양
- hash 함수가 non-uniform하기 분배한 경우
- multiple record가 같은 search-key값을 가진 경우
overflow chaining (closed addressing, closed hashing)
→ linked list로 해결
Example of Hash Index
Deficiencies of Static Hashing
DB는 시간이 지남에 따라 grow하거나 shrink하는데, static hash index이기 때문에 db가 커지면 성능이 안 좋아지고, 작아지면 공간이 낭비됩니다.
이에 대한 해결책은,
- periodic re-organization with a new hash function → cost가 비싸다
- Dynamic Hashing (better soultion)
Dynamic Hashing
수준을 벗어나는 것 같아 자세히 다루지 않았습니다.
- Linear Hashing
- Extendable Hashing
Ordered Indexing vs Hashing
- 주기적으로 B+ tree를 다시 만든다.
- access time의 경우 B+tree는 무조건 leaf까지 가야하고, hash는 경우에 따라 다르다.
- Hashing ⇒ 특정 값을 찾는 쿼리에 적합하다.
- B+ Tree ⇒ range 쿼리에 적합하다.
Multiple (Single-Attrivute) Indices
- record개수가 적을수록 selectivity가 좋은 것이다.
- query optimizer가 전략 중에서 가장 효율적인 것을 선택하여 실행한다.
- 전략 개수 : nC1 + nC2 + ….. + nCn
Indices on Multiple Search Keys
Creation of Indices
create index <index name> on <relation name> ( <attribute들 목록(1개~n개)> )
24.3 Bitmap Indices
- bit를 이용하여 coulmn 값을 저장하고 rowId를 자동으로 생성
- key값에 중복이 없고, key 값 별로 하나의 bitmap record를 가짐
- bitmap은 relation에 비해 매우 작다.
- bitmap 상의 각 bit가 하나의 테이블 reocrd와 mapping
- 데이터의 위치를 bit로 표시하고, 있으면 1, 없으면 0이다.
- multiple attribute에 대한 쿼리를 수행할 때 유용하다.
위 그림에서 gender에 대한 bit가 10010이면 bitmap에서 매칭되는 m을 가리킵니다.
- using bitmap operation : Intersection(and), Union(or)
위 그림에서 male이면서 income_level이 L2인 record를 select하기 위해서는
01101 and 01000 = 01000 bitmap을 연산하여 구합니다.
24.4 Indexing of Spatial Data
DB에 선, 다각형과 같은 geometry, geography data 형식을 저장할 수 있습니다.
이를 통해 서로 가장 가까운 위치를 찾는다거나, 특정 spatial region에 포함되는 point를 찾을 수도 있습니다.
k-d tree
- 공간을 기반으로 partitioning하는 binary tree
- 각 level에서 공간은 두 개로 나눠진다.
k-d B tree
- multiple child 허용
Quadtree
- non-leaf node는 4개의 정사각형으로 공간이 나누어진다.
- leaf node에는 0개~max개의 point들이 들어있다.
R-Trees
B+ Tree에서 다차원 검색이 가능하도록 확장한 형태입니다.
- 공간을 bounding box(최소 경계 사각형)로 분할하여 저장한다.
- bounding box끼리는 겹칠 수 있다.
- 모든 leaf node는 같은 depth
- 모든 record는 leaf node에서만 mapping
- 한 node에 있는 영역들이 서로 겹칠 수 있으므로, 검색 경로가 유일하지 않다.
위 그림에서 점선으로 표시된 구역이 하나의 bounding box입니다.
Indexing Temporal Data
- 기간을 나타내는 data
만약 a = v 이면서 time t 동안 valid한 record를 select 해야한다면?
⇒ a와 time을 각각 하나의 차원으로 만들고 spatial data로 사용한다.
- 하지만 이때, 값의 범위가 매우커서 공간 index로 활용하기에 부적절하다.
⇒ 모든 tuple을 (a, start time)으로 indexing된 곳에 저장한다.
⇒ search for range (a, 0) to (a,t)