B tree가 왜 DB 인덱스(index)로 사용되는가?

DB는 secondary storage 에 저장된다

• 데이터 보존이 영구적, 대용량의 메모리 영역이기 때문
• 메인 메모리에 비해 access 속도가 매우 느림
  • 따라서, secondary storage로의 접근 횟수를 줄여주는 것이 유리하다.

B 계열 트리 vs Balanced BST 트리

• 조회, 삽입, 삭제의 시간복잡도 관점에서 봤을 때 위의 트리들은 모두 O(logN)으로 같다.
• 그렇다면 B 계열 트리를 쓰는 이유는 무엇일까?
  • B 계열 트리(ex. 5차 B tree)의 경우 자녀 노드 수가 3-5개 이고, Balanced BST의 한 종류인 AVL 트리의 경우 자녀 노드 수가 1-2개 이기 때문에 데이터를 찾을 때 탐색 범위를 더 빠르게 좁힐 수 있다.
  • 노드가 가질 수 있는 key값이 5차 트리의 경우 2-4개 AVL 트리의 경우 1개이고, secondary storage에서 데이터를 block 단위로 가져오기 때문에 B 트리를 사용할 때 access 횟수가 줄 확률이 더 크다.

B 트리의 강력함

• 101차 B 트리 (최대 자녀 수 101개, 최대 key값 100개) 가 저장할 수 있는 데이터 수
• 높이 3 (레벨4) 인 경우
  • Best case: 약 1억개
  • Worst case: 약 26만개

해시 기법을 쓰면?

• 해싱(hash) 기법은 삽입/조회/삭제에 O(1) 이기 때문에 이 점에서는 이점이 있다.
  • 그렇지만 정확한 값을 조회하는 equality 조회만 가능하고 (범위 조회 X)
  • 정렬에 사용할 수 없다는 점이 문제가 된다.