[Database] - Hash index / B-Tree index

Hash index

• B-tree 만큼 일반적/범용적으로 사용되지는 않지만 고유의 기능과 특성을 가지고 있는 인덱스 오브젝트 입니다.
• 실제 키 값과 관계없이 인덱스 크기가 작고 검색이 빠르다는 것 입니다.
• 원래의 값을 저장하는 것이 아닌 해시 함수의 결과만을 저장하게 됨에 따라 키 컬럼 값은 4~8바이트 정도로 작은 길이로 줄어듭니다.
• Hash된 데이터 값에 따라 저장될 버킷 위치를 정하기 때문에 빠른 속도로 검색 영역을 제한할 수 있다.
• 버킷의 범위가 작다면 Collision이 발생하게 되어 효율이 떨어지게 됩니다.
• 해시 인덱스는 정렬되어 있다고 볼 수 없다.
• 메모리기반의 테이블에 주로 사용된다.
• 자주 사용되는 데이터를 옵티마이저가 판단하여 해시 키로 만들기 때문에 제어가 어렵다.
• E.g) Adaptive Hash Index

생각을 하여 보면 B-Tree를 사용하여 매번 검색을 한다고 할 때 N개의 Data가 들어온다면 O(NLogN)의 시간 복잡도가 걸립니다.

자주 사용하는 데이터가 존재할 것이고 이를 매번 검색할 때마다 O(LogN) 걸리게 된다면 비효율적이지 않을까요?

자주 사용하는 데이터에 대해 O(1)로 처리한다라는 개념이 Hash index입니다.

 

 

B-Tree index

• B-Tree 인덱스는 항상 정렬된 상태를 유지한다.
• 항상 정렬된 상태를 유지하기 위해서는 삽입,삭제,업데이트 시 Page를 다시 설정하기 위해 시간이 소요된다.
• 대부분의 RDBMS에서 기본적으로 사용된다.
• 다중 Column Index를 사용할 수 있다.