B+트리? B-트리?
B-트리는 각 노드는 여러개의 key를 가질 수 있으며 여러개의 Child를 가질 수 있다. 또한 모든 리프 노드는 동일한 depth를 가지고 있다. 키는 B-트리 알고리즘에 따라 정렬되어 각 노드에 배치
각 노드는 최대 2개의 key를 가지며 최대 3개의 자식을 가질수 있다.
각 노드에는 여러개의 키를 갖고 키에 대응하는 데이터도 함께 갖는다. 하나의 노드에 여러개의 키를 갖는다.
B+트리는 b-트리를 개량한 트리로 b-트리처럼 모든 리프 노드에 동일한 depth를 가지지만 b+ 트리는 inner 노드에는 키만 저장이 되고 리프 노드에는 키와 데이터를 함께 저장한다는 것이다. 리프 노드에만 데이터가 저장되기 때문에 리프간의 포인트를 연결 b-트리에 비해 쉬운 순회가 가능 inner Node에는 데이터가 없기때문에 b-트리의 inner 노드에 비해 용량이 작아 많은 inner노드의 배치가 가능하다.
B+tree의 장점 1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음) 2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다
김개발