[데이터베이스] 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)