B tree - index
왜 DB index로 B tree 계열이 사용되는가? B+ tree B* tree
시간 복잡도
B tree
BST : 조회 O(N) // 삽입, 삭제 O(1)
B tree : 조회, 삽입, 삭제 O(logN)
self-balancing BST와 비교
B tree와 self-balancing BST 양쪽다 조회, 삽입, 삭제 시간복잡도는 O(logN)
컴퓨터 구조
CPU : 프로그램 코드가 실제로 실행되는 곳
Main memory(RAM) : 실행 중인 프로그램의 코드들과 코드 실행에 필요한 혹은 그 결과로 나온 데이터들이 상주하는 곳.
휘발성 메모리(파워를 off하면 데이터들이 사라진다.)
Secondary storage(SSD,HDD) : 프로그램과 데이터가 영구적으로 저장되는 곳,
실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳.(swap, 프로그램에서 자주 사용하지 않는 데이터를 저장한다.)
Secondary storage
-
데이터 베이스가 저장되는 공간
-
데이터를 처리하는 속도가 가장 느리다.
-
데이터를 저장하는 용량이 가장 크다.
-
block 단위로 데이터를 읽고 쓴다.
block: file system이 데이터를 읽고 쓰는 논리적인 단위
block의 크기는 2의 승수로 표현되며 대표적인 block size는 4KB, 8KB, 16KB 등이 있다.
1KB씩 데이터를 메인 메모리로 보내는것보다 효율적인 처리가 가능하다.
단점 : 불필요한 데이터까지 읽어올 가능성이 있다.
Database 예시
AVL tree index vs B tree index
AVL tree index
루트 노트를 제외한 노드들은 secondary storage에 존재한다.
AVL tree는 secondary storage에 네 번 접근
where b = 5;
3 - secondary storage 접근
4 - secondary storage 접근
5 - secondary storage 접근
tree를 통해 인덱스 파악 후 secondary storage 접근하여 데이터 출력B tree index
5차 B tree (자식 노드가 최대 5개)
B tree는 secondary storage에 두 번 접근
where b = 5;
5 - secondary storage 접근
tree를 통해 인덱스 파악 후 secondary storage 접근하여 데이터 출력차이점
AVL tree index를 통해 데이터를 가져오기 위해 B tree index보다 더 많은 secondary storage에 접근해야한다.
why?
-
B tree의 경우 자녀 노드의 수가 3~5개인 반면, AVL tree는 1~2개이다.
즉, B tree의 경우 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다. -
노드가 가질 수 있는 데이터의 수에서 차이가 존재한다.
secondary storage에서 데이터를 가져올 때 block단위로 가져오기 때문에 B tree의 경우 block에 사용할 수 있는 데이터를 더 많이 가져올 수 있는 반면, AVL tree는 필요없는 데이터가 포함되어 올 경우가 많다.
B tree의 장점
if) 101차 B tree
best case
각 노드가 모두 자녀 노드를 101개씩 가지고, key를 100개 가지고 있다 가정해보자.
tree의 높이 3개인 경우 데이터의 갯수가 약 1억개 저장 가능하다.
worst case
최소 자녀 수 와 최소 key 수 조건은 root node는 예외이다.
worst case : root node의 key는 1개이고, 자녀 노드가 2개이다.
약 26만개 저장 가능하다.
average case
루트 노드의 데이터 수는 2<j<100이고, 자녀노드의 최소 key의 갯수 50<k<100
저장 가능한 데이터의 수 : 260,000 < 전체 데이터 수 < 100,000,000
- 네 개의 level만으로 수 백만 ~ 수 천만 개의 데이터를 저장할 수 있다.
- root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있다.
결론
