Database

[Indexing] B-트리 (B-Tree) 탐색

B-트리 란?B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 라는데.. 인덱싱이니 탐색 효율을 늘리는 방법인건 알겠는데코딩테스트를 준비하면서 익숙한게 아니라면 어색할 수도 있다.위의 정의는 보고 감만 잡아보고 그림으로 이해 해보자   이런식의 트리 구조 형태로 B-tree가 있다고 해보자총 3개의 계층 구조로 나눠져 있으니 3차 B-tree라고 볼수있다. 눈에 보이는 직관적인 그대로 값을 크기기준으로 나눠서 자식노드를 찾아가는 방법으로조회하는 데이터의 수를 줄인것이다. 예를들어 2라는 값을 찾고자 하면 맨 처음 루트노드에서 10, 20이란 2가지의 기준으로 ..