Database의 index로 B Tree를 사용하는 이유

B Tree, AVL tree와 Red-Black tree 모두 조회, 삽입, 삭제 모두 평균과 최악이 OlogN 인데 왜 DB의 index로 B Tree를 사용할까?

보조기억장치(Secondary storage) 특징

• 처리하는 속도가 가장 느리다
• 데이터를 저장하는 용량이 가장 크다
• block 단위로 데이터를 읽고 쓴다
  • block : file system이 데이터를 읽고 쓰는 논리적인 단위, blcok의 size는 2의 승수로 표현
  • 단점 : 불필요한 데이터까지 읽어올 가능성이 있다.

Database는 보조기억장치(Secondary storage)에 저장된다.

• DB에 데이터 조회할 때 보조기억장치에 최대한 적게 접근하는 것이 성능 면에서 좋다.
• block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.

AVL tree index

5라는 데이터를 조회하고 싶을 시

1. root데이터와 비교
2. 왼쪽(혹은 오른쪽)자녀 데이터를 보조기억장치에서 조회 후 메인 메모리에 올린다
3. 자녀 노드와 데이터 비교
4. 왼쪽(혹은 오른쪽)자녀 데이터를 보조기억장치에서 조회 후 메인 메모리에 올린다
5. 반복

데이터를 읽을 때 마다 보조기억장치를 조회

B Tree index

5라는 데이터를 조회하고 싶을 시

1. root데이터와 비교
2. 4와 8사이의 자녀노드를 보조기억장치에서 조회 후 메인 메모리에 올린다
3. 목표 데이터를 찾았을 시 해당 데이터 포인트가 가리키는 데이터를 보조기억장치에서 조회

B tree를 선택하는 이유

1. 1/2씩 탐색 범위를 줄여 나가는 AVL과는 다르게 1/M으로 줄여나가는 B tree index를 사용하면 탐색범위를 빠르게 좁혀 보조기억장치 접근을 줄일 수 있다.
2. 노드의 데이터 수도 AVL은 1개지만 B tree는 M개라 보조기억장치에서 조회 block을 가져올 때 훨씬 사용할 가능성이 높은 데이터를 가져오게 된다.

예외 Hash index를 쓰는건?

조회, 삽입, 삭제 모두 상수 시간이 소요되지만 equality(=) 조회만 가능하고 범위 기반 검색이나 정렬에는 사용될 수 없다.