왜 데이터베이스 인덱스로 B tree 계열을 사용할까?
데이터베이스 인덱스 테이블을 구현할 때 트리 구조의 B+Tree와 B-tree 인덱스 방식을 많이 사용한다. B tree의 시간 복잡도는 O(log N)으로, B tree 인덱스를 사용하면 데이터의 삽입, 갱신, 삭제 등에 드는 작업 비용을 줄일 수 있기 때문이다. 그런데 균형 이진 탐색 트리인 AVL Tree와 Red-Black Tree도 시간 복잡도 O(log N)으로, B Tree와 시간 복잡도가 동일하다. B 트리의 시간 복잡도 O(log N) 균형 이진 탐색 트리 시간 복잡도 O(log N) 둘 다 O(log N)인데 왜 균형 이진 탐색 트리가 아닌 B 트리 계열을 인덱스로 사용하는 걸까? 잠시 컴퓨터 구조를 살펴보도록 하자. CPU(Central Processing Unit, 중앙 처리..
