(3부) B tree가 왜 DB 인덱스(index)로 사용되는지를 설명합니다

https://youtu.be/liPSnc6Wzfk

B tree의 시간복잡도(B+ tree, B* tree 포함) : 조회/삽입/삭제 => avg & worst case = O(log N)

  

Computer system

CPU : 프로그램 코드가 실제로 실행되는 곳

Main memory(RAM) : 실행 중인 프로그램의 코드들과 코드 실행에 필요한 데이터, 혹은 그 결과로 나온 데이터들이 상주하는 곳

Secondary storage(SSD or HDD) : 프로그램과 데이터가 영구적으로 저장되는 곳(<=> RAM). 실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳. 데이터베이스도 여기에 저장!

  

Secondary storage

데이터를 처리하는 속도가 가장 느리다.

데이터를 저장하는 용량이 가장 크다.

block 단위로 데이터를 읽고 쓴다.

- block 단위 : file system이 데이터를 읽고 쓰는 논리적인 단위. block의 크기는 2의 승수로 표현되며 대표적인 사이즈는 4KB, 8KB, 16KB 등이 있다. 불필요한 데이터까지 읽어올 가능성이 있다.

  

Database

DB는 secondary storage에 저장된다.

DB에서 데이터를 조회할 때 secondary storage에 최대한 적게 접근하는 것이 성능 면에서 좋다.

block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.

  

AVL tree vs B tree

B tree의 자녀 노드 수↑ : 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.

B tree 노드의 데이터 수↑ : block 단위에 대한 저장 공간 활용도가 더 좋다.

  

B tree의 강력함

적은 level만으로 수 백만, 수 천만 개의 데이터를 저장할 수 있다.

root 노드에서 가장 멀리 있는 데이터도 적은 이동으로 접근할 수 있다.

  

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

DB는 기본적으로 secondary storage에 저장된다.

B tree index는 self-balancing BST에 비해 secondary storage 접근을 적게 한다.

B tree 노드는 block 단위의 저장 공간을 알차게 사용할 수 있다.