B+-Tree를 사용하여 Key 기반 검색을 할 경우 disk I/O가 매우 적은 이유는?

SW-H commented 1 year ago

하나의 Node에 여러개의 Key를 갖는다
B+ Tree의 Inner Node는 Data가 없기 때문에 B-Tree의 Inner Node에 비하여 용량작다 -> 하나의 Disk Block에 더 많은 Inner Node를 배치 할 수 있다
Node 하나의 크기를 Disk Block 크기와 일치시켜서 CPU가 Disk에 접근하는 I/O Access 횟수를 최소화한다 (∵ Disk의 특정 데이터에 접근할 때, Disk내에서 특정 데이터가 위치한 Disk Block 전체를 Loading한다)

anuu0916 commented 1 year ago

하나의 Node에 여러개의 Key를 갖는 특성 때문에 용량이 큰 Block 단위로 Data를 Read/Write하는 Disk 환경에서는 Binary Search Tree보다 B-Tree를 이용하는 것이 유리하다.

출처 : https://ssup2.github.io/theory_analysis/B_Tree_B+_Tree/

anuu0916 commented 1 year ago

이진 트리의 결정적인 단점은 하나의 부모가 두 개의 자녀밖에 가지지 못한다는 점입니다.이렇게 되면 트리의 높이가 높아지게 됩니다. 트리의 성능은 트리의 높이에 달려있기에 성능 저하를 불러올 수 있습니다. 따라서 대용량 데이터를 처리할 수 없게 됩니다. 즉 검색 효율이 트리의 균형에 의존적이라서 최악의 경우, 시간복잡도가 선형이 되어버릴 수 있습니다. 이런 경우는 아마 자식 노드들이 모두 오른쪽으로 쏠린 경우일 것입니다. 이를 피하기 위해선 이진트리의 균형을 자동적으로 맞춰줄 수 있는 로직이 필요합니다. 이렇게 어렵게 이진트리를 쓸 바에야, 그냥 B-tree 를 쓰는 것이 더 나을 것입니다.

출처 : https://steemit.com/algorithms/@soladola/b-tree

jinsusong / CS-Study

B+-Tree를 사용하여 Key 기반 검색을 할 경우 disk I/O가 매우 적은 이유는? #73