28. B tree 3부 : DB 인덱스로 쓰는 이유

본 내용은 유튜버 쉬운코드의 강의 "데이터베이스"를 참고하여 작성하였습니다.

 

왜 DB index로 B tree 계열이 사용되는가?

시간복잡도 계산

• B tree나 self-balancing BST 둘다 시간복잡도는 O(log N)

---

컴퓨터 시스템

컴퓨터 구조

• CPU : 프로그램 코드가 실제로 실행되는 곳
• Main memory(RAM) : 실행 중인 프로그램의 코드들과 코드 실행에 필요한 혹은 그 결과로 나온 데이터들이 상주하는 곳
• Secondary storage(SSD or HDD) : 프로그램과 데이터가 영구적으로 저장되는 곳, 실행 중인 프로그램의 데이터가 일부로 임시 저장되는 곳
  
  • Main memory의 용량이 작으므로 Secondary storage에 있는 데이터와 swap 할 수도 있음.
  • database도 여기에 저장됨.

 

Secondary storage의 특징 

• 데이터를 처리하는 속도가 가장 느리다.
• 데이터를 저장하는 용량이 가장 크다.
• block 단위로 데이터를 읽고 쓴다. -> 불필요한 데이터까지 읽어올 가능성이 있음.
  • block : file system이 데이터를 읽고 쓰는 논리적인 단위
  • block의 크기는 2의 승수로 표현되며, 대표적인 block size는 4KB, 8KB, 16KB 등이 있다.
• DB에서 데이터를 조회할 때 secondary storage에 최대한 적게 접근하는 것이 성능 면에서 좋음.
• block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있음. -> 그래서 B tree 사용

---

인덱스로 성능 비교하기 (AVL tree index(b) vs B tree index(b))

예시 테이블

가정

• tree의 각 노드는 서로 다른 block에 있다고 가정
• 초기에는 root 노드를 제외한 모든 노드는 secondary storage에 있다고 가정
• 초기에는 데이터 자제도 모두 secondary storage에 있다고 가정

 

AVL tree / 5차 B tree

	AVL tree	5차 B tree
secondary storage	4번 접근	2번 접근
자녀 노드 수	1~2개	3~5개
노드의 데이터 수	1개	2~4개

• 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.
• block 단위에 대한 저장 공간 활용도가 좋다.

---

101차 B tree 데이터 총 개수

최대 자녀 수 101    /   최대 key 수 100   /   최소 자녀 수 51 (* leaf 노드, root 노드 제외)   /   최소 key 수 50 (* root 노드 제외)

 

Best case일 때 / Worst case일 때

Best case / Worst case

 

Avg case일 때

avg case

• 265301 < 전체 데이터 수 < 104060400
• 네 개의 level만으로 수 백만, 수 천만 개의 데이터를 저장할 수 있다.
• root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있다.

---

B tree 계열을 DB 인덱스로 사용하는 이유

• DB는 기본적으로 secondary storage에 저장된다.
• B tree index는 self-balancing BST에 비해 secondary storage 접근을 적게 한다.
• B tree 노드는 block 단위의 저장 공간을 알차게 사용할 수 있다.

---

self-balancing BST와 hash index를 쓰는 건?

• self-balancing BST의 노드들도 block 안에 최대한 담는다면?
  -> 그게 결국 B tree 동작 방식
• hash index
  -> 삽입/삭제/조회의 시간 복잡도가 O(1)이지만, equality(=) 조회만 가능하고 범위 기반 검색이나 정렬에는 사용될 수 없음.