B-트리 삽입·분할 계산기

트리가 깊어지는 것이 뿌리가 갈라질 때뿐이기 때문입니다. 키는 언제나 잎에 들어가고, 잎이 넘치면 가운데 키를 부모로 올려 보내며 둘로 갈라집니다. 이것이 위로 번져 뿌리까지 넘치면 그때 새 뿌리가 생기는데, 그러면 모든 잎이 한꺼번에 한 칸씩 깊어집니다. 그래서 어느 키를 찾든 읽는 블록 수가 같습니다.

어느 쪽으로도 가지 않고 부모로 올라갑니다. 부모에서 두 자식을 가르는 칸막이 노릇을 하기 때문입니다. 키가 m−1개인 노드가 하나 더 받아 m개가 되면 가운데 하나를 빼고 남은 m−1개가 절반씩 나뉘며, 양쪽 모두 최소 키 개수 ⌈m/2⌉−1을 채웁니다.

디스크 블록 하나에 노드가 딱 들어가도록 정합니다. 디스크에서는 블록 하나를 읽는 값이 크고 그 안에서 키를 찾는 값은 거의 공짜라, 노드를 블록 크기에 맞추고 차수를 수백까지 올립니다. 그러면 수백만 건짜리 인덱스도 높이가 서너 층에 그칩니다. 이 계산기는 눈으로 따라갈 수 있도록 3~8까지만 다룹니다.

균형이 저절로 유지되고, 노드 하나에 키가 여러 개 들어갑니다. 이진 탐색 트리는 정렬된 키를 차례로 넣으면 한 줄로 늘어져 높이가 키 개수만큼 되어 버리지만, B-트리는 넘칠 때마다 갈라져 높이가 로그로 유지됩니다. 이 계산기에 «1 2 3 4 5 …»를 넣어 확인해 보십시오.

B+트리는 값이 잎에만 있고 위 층은 길잡이 키만 갖습니다. 위 층에 값이 없어 한 블록에 키를 더 많이 담을 수 있어 높이가 낮아지고, 잎끼리 옆으로 이어져 있어 범위 훑기가 빠릅니다. 실제 데이터베이스 인덱스는 거의 B+트리이며, 이 계산기가 다루는 것은 값이 모든 층에 있는 원래의 B-트리입니다.

결과 트리가 조금 다를 수 있습니다. 이 계산기는 먼저 잎에 넣고 넘치면 위로 올려 보내는 방식을 쓰는데, 내려가는 길에 가득 찬 노드를 미리 갈라 두는 방식(CLRS)도 널리 쓰입니다. 어느 쪽이든 «모든 잎의 깊이가 같다», «키 개수가 ⌈m/2⌉−1 이상 m−1 이하다», «중위 순회가 정렬 순서다»라는 세 조건은 똑같이 지켜집니다.

두 번째부터는 넣지 않고 걸러 냅니다. 결과 표에 걸러진 키를 따로 보여 주며, 실제 인덱스에서는 중복 키를 허용하는 구현도 있고 금지하는 구현도 있습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 입력한 키는 이 기기에만 남습니다.