인덱스가에 Hash보다 B-TREE를 쓰는 이유?

Buckets (Hash Table)는 O(1)로 탐색시간이 빠르다

• Hash 함수는 입력 값(keys)이 들어오면 언제나 같은 출력 값(Hash 값)을 가짐
• buckets의 index 값으로 매핑되어 찾고자 하는 데이터를 얻을 수 있음
• 미리 저장된 메모리 공간(buckets)에 한 번에 접근을 하기 때문에, 탐색 시간이 O(1)로 빠름
  • Hash 값이 충돌이 일어나는 등의 최악의 경우, O(N)이 될 수도 있음

 

 

 

 

탐색시간이 빠른 Hash가 인덱스로 적절하지 않은 이유

• 단 하나의 데이터를 탐색하는 시간이 O(1)으로 빠른 것이다.
• Hash Table에 저장되는 값들은 정렬되어 있지 않기 때문에 특정 값보다 크거나 작은 값을 찾을 수 없다.
• SQL 쿼리문에서 특정 범위의 값을 조회하는 경우, 특정 값보다 크거나 작은 값을 찾을 수 없다.

해시 인덱스는 검색하고자하는 값을 해시함수에 입력한 후 그 결과와 Bucket의 내용과 비교하여 해당 데이터 레코드의 위치를 찾을 수 있는 인덱스 기법이다.

SELECT .. FROM tb_hash WHERE column >= '검색어';
SELECT .. FROM tb_hash WHERE column BETWEEN 100 AND 120;
SELECT .. FROM tb_hash WHERE column LIKE '검색어%'
SELECT .. FROM tb_hash WHERE column <> '검색어';

 

• 범위 비교나 부정형 비교가 포함된 SQL 쿼리는 해시 인덱스를 사용할 수 없다.

 

 

 

---

 

 

평균 Tree의 탐색 시간복잡도 : O(logN)

 

 

최악 Tree의 탐색 시간복잡도 : O(N)

• 최악의 경우를 대비해서 Balanced Tree를 사용한다.

 

B Tree -- Balanced Tree -- 균형잡힌 Tree

• 최악의 경우처럼 트리가 한쪽으로 쏠리지 않게 트리가 재정렬
• 노드 삽입 및 삭제 시에 특정 규칙에 따라 좌 / 우 SubTree의 밸런스를 유지하는 Tree

 

 

• 탐색에 대한 시간 복잡도 : 언제나 O(logN)
• 노드 삽입, 삭제, 변경 --> 트리 재정렬 작업 --> 일반적인 Tree보다 시간복잡도 성능이 좋지 않음

 

 

 

 

 

 

 

출처

siAhn, https://siahn95.tistory.com/entry/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EB%9E%80-2-%EA%B5%AC%EC%A1%B0-B-Tree-%EA%B3%84%EC%97%B4%EC%9D%84-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0?category=821999 

[DB] 인덱스란? - (2) 구조, B-Tree 계열을 쓰는 이유

jsj3282, https://velog.io/@jsj3282/17.-%ED%95%B4%EC%8B%9CHash-%EC%9D%B8%EB%8D%B1%EC%8A%A4

17. 해시(Hash) 인덱스