- B tree 계열 시간복잡도 : log N
- BST의 경우 최악의 경우(한쪽으로 쏠린 현상) O(N)을 띔.
- 스스로 균형있게 조절하는 AVL tree와 Red-Black tree의 경우 O(logN)을 나타냄
- 그러면 왜 B 트리인가?
- computer system
- CPU : 프로그램 코드가 실제로 실행되는 곳
- RAM : 실행중인 프로그램의 코드들과 코드 실행에 필요한 혹은 그 결과로 나온 데이터들이 상주하는 곳
- Secondary Storage(SSD or HDD) : 프로그램과 데이터가 영구적으로 저장되는 곳, 실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳(SWAP)
- 데이터를 처리하는 속도가 가장 느린 특징
- 데이터를 저장하는 용량이 가장 크다
- block 단위로 데이터를 읽고 쓴다
- file system이 데이터를 일고 쓰는 논리적 단위
- block의 크기는 2의 승수로 표현, 4KB, 8KB, 16KB 등이 있다.
- 불필요한 데이터까지 읽어올 가능성이 있다.
- DB는 Secondary Storage에 저장
- DB에서 데이터를 조회할 때 Secondary Storage에 최대한 적게 접근하는 것이 성능 면에서 좋다.
- Block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.
B tree를 사용했을 때 장점
(1) 데이터를 찾을 때 탐색 범위를 빠르게 좁힐 수 있다.
- ex) 5차 B tree => 각 노드의 최소 자녀의 수 : 올림(M/2) -> 3개
- ex) AVL Tree index => 각 노드의 최대 자녀 수 2개
- 자녀 노드의 수가 더 많으므로, 탐색 시 탐색 범위가 훨씬 더 줄어들기에 Secondary Storage에 덜 접근하기에 유리해짐
- ex) B tree 자녀 3개 -> 탐색 범위가 1/3씩 줄어듦 -> 리프노드까지 가기에 더 빠름
(2) block 단위에 대한 저장 공간 활용도가 더 좋다
-
Secondary Storage에서 데이터를 가져올 때 block단위로 읽어올 때 활용도가 더 좋다.
-
BST의 경우 노드 1개와 나머지 불필요 data를 가져오는 반면, B tree의 경우 노드에 포함된 데이터가 포함된 블락 단위이기에 효율성이 더 좋다(의미있는 데이터 ↑)
- 각 노드의 최대 key 수 : M-1 / 각 노드의 최소 key 수 : 올림(M/2) -1
- ex) 5차 B tree -> 최대 key 4개 / 최소 key 2개
- ex) 리프노드에 데이터 4개 있다고 가정 -> 블락단위로 가져올 때 의미있는 데이터 4개 / BST의 경우 리프노드 데이터 1개 --> 블락단위로 가져올 때 의미있는 데이터 1개
-
4개의 level만으로 수 백만, 수 천만개의 데이터 저장 가능
- root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있다.
- 엄청 많은 양의 데이터를 저장하기에 활용하기 좋은 인덱스 구조
결론
- B tree 계열을 DB 인덱스로 사용하는 이유
(1) secondary storage 접근 적게 함
(2) block 단위의 저장 공간을 알차게 사용할 수 있다. - hash index를 사용하지 않는 이유
- 삽입/삭제/조희의 시간 복잡도 O(1) 이지만 equality(=) 조회만 가능
- 범위 기반 검색이나 정렬에는 사용될 수 없다는 단점
- equality만 할 경우라면 hash가 이점
비슷한 어려움을 겪는 누군가에게 도움이 되길