왜 많은 DB의 인덱싱은 hashtable이 아닌 b-tree로 구현되어 있을까?

hashtable을 이용하면 해당 값에 접근하는 시간이 O(1)으로 일정한데 반해

b-tree를 이용한다면 O(logn)으로 압도적인 성능 차이를 보인다.

얼핏 생각하기에 hashtable로 구현한다면 훨씬 빠를 것같은데 왜 대부분의 DB의 인덱싱은 b-tree로 구현되어 있는걸까?

 

해시테이블

장점

특정한 값에 대해 O(1)의 시간으로 접근할 수 있다

insert와 delete 시에 인덱싱 관리가 효율적이다

구현하기 쉬움

 

단점

정렬이 효율적이지 못 하다

데이터 전체 크기가 커지면 커질수록 해시 충돌 문제에 의해 효율이 떨어진다

B-tree

장점

예상 가능한 순서로 순회를 한다 (작은 값에서 큰 값으로 혹은 큰 값에서 작은 값으로)

제한 조건이 걸린 조회에서 효율적이다 (e.g. 'abc'로 시작하는 모든 값)

범위 검색이 효율적이다

 

단점

insert와 delete 시에 지속적으로 tree를 관리해줘야 하는 비용이 들어간다

 

결론

DB의 존재는 단순히 특정값의 존재 여부에 대한 결과값만을 확인하는 것이 아닌 특정 조건을 걸거나 제한을 둬서 범위 검색을 쿼리하는 등 다양한 기능을 할 수 있어야 하고

데이터 크기가 늘어나더라도 유지 관리가 쉬워야 한다는 점 등에 의해 b-tree를 통해 인덱싱을 할 수 있음을 알 수 있다.

 

 

레퍼런스

https://www.quora.com/If-Hash-Map-has-the-search-complexity-of-O-1-and-B-tree-has-O-Log-n-why-does-the-database-index-use-B-tree-and-not-Hash-Map

If Hash Map has the search complexity of O(1) and B tree has O(Log n), why does the database index use B tree and not Hash Map?

https://www.quora.com/A-B-tree-index-is-better-than-a-hash-index-Why

A B-tree index is better than a hash index. Why?