DB 인덱스에서 Hash보다 B-TREE 를 사용하는 이유

기본적으로 Hash Table은 탐색속도가 빠른 자료구조에용

그런데 왜 DB 인덱스에서는 Hash 가 아닌 B-TREE 구조를 사용할까용?

 

B-Tree (Balanced Tree) 의 탐색 시간 복잡도는 O(logN) 에용

인덱스에 일반적으로 사용되는 자료구조는 B+TREE 구조에용

 

 

Hash Table

해시 테이블은 연관배열 구조를 이용해 key 에 value 를 저장하는 자료구조에용

 

연관배열구조 = key와 value 가 1:1 로 매칭되어있는 자료구조, key를 통해 value를 도출할수있음

 

해시 테이블의 Search(검색) 의 시간 복잡도는 기본적으로 O(1)이다.

KEY에 매칭되는 VALUE 를 바로 찾기 때문이다.

 

 

그런데 이렇게 탐색시간이 빠른 Hash가 왜 인덱스에서 사용 되지 않을까용?

 

해시 테이블에 저장되는 값들은 정렬이 되어있지 않기 때문에 , 특정값보다 크거나 작은값을 찾을 수가 없어용.

 

해시 테이블은 동등연산(=)에 특화 되어있고 위의 특징을 가지기 때문에,

SQL 쿼리문에서 특정범위 ( > , < ) 값을 조회하는 경우에 찾을 수 없고 따라서 데이터베이스 자료구조에 적합하지 않아용.