B+tree

[B+tree가 DB index를 위한 자료구조로 적합한 이유]

1. 항상 정렬된 상태를 유지하여 부등호 연산에 유리하다.
2. 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 갖는다.

Hash index

hash index는 빠른 데이터 검색$O(1)$이 필요할 때 유용하다. 하지만 index로써 hash index가 사용되는 경우는 제한적이다. 왜냐하면 hash index는 등호(=) 연산에만 특화되었기 때문이다. 데이터가 조금이라도 달라지면 hash function은 완전히 다른 hash 값을 생성하는데, 이러한 특성 때문에 부등호 연산(>, <)이 자주 사용되는 DB 검색에는 hash index가 적합하지 않다.

면접 질문

1. 데이터를 검색을 할 때 hash table의 시간 복잡도는 $O(1)$이고 b+tree는 $O(logn)$으로 더 느린데 왜 index는 hash table이 아니라 b+tree로 구현되나요?

   Hash table을 사용하면 하나의 데이터를 탐색하는 시간은 O(1)로 b+tree보 다 빠르지만, 값이 정렬되어 있지 않기 때문에 부등호를 사용하는 query에 대해서는 매우 비효율적이게 되어 데이터를 정렬해서 저장하는 b+tree를 이용합니다.