Relaxed Radix Balanced 트리 | Peter Horne-Khan

저는 제가 만드는 언어 Ivan에 불변 벡터(immutable vector)를 추가하려고 하고, 이를 위해 적합한 자료구조를 선택할 필요가 있었습니다. Clojure는 '거의' 상수 시간의 조회, 갱신, append를 지원하는 Persistent Vector(PV) 구조를 사용하지만, 효율적인 삽입이나 병합이 어렵다는 단점이 있습니다. Bagwell과 Rompf가 2011년에 제안한 Relaxed Radix Balanced(RRB) Tree는 바로 이러한 한계를 해결합니다.

RRB 트리가 어떻게 동작하는지 제대로 이해하려면 여러 논문을 읽어야 했기에, 조금 더 쉽게 이해할 수 있도록 이 글을 정리해봤습니다. 주요 작동 방식과 직관을 전하면서, 수학적 세부 내용은 논문에 맡기겠습니다.

여러분이 Persistent Vector의 작동 방식에 익숙하다고 가정합니다.

Persistent Vector 병합

두 Persistent Vector를 병합한다고 가정해봅시다.

Radix 탐색이 제대로 동작하도록 하기 위해 모든 노드(오른쪽 엣지 제외)가 고정 크기의 자식(M개)을 가지도록 해야 합니다. 이러한 트리는 _좌측 밀집(leftwise dense)_되어 있다고 말합니다. 이 예에서 왼쪽 벡터의 마지막 자식이 2개의 요소밖에 없으므로, 오른쪽 벡터에서 2개의 요소를 넘겨야 균형이 맞춰집니다. 이로 인해 오른쪽 벡터의 첫 자식의 균형도 깨져 연쇄적으로 균형을 맞춰야 하며, 상당히 많은 새로운 노드(오렌지색 부분)를 생성해야 합니다. 이는 오른쪽 벡터의 크기에 비례해 비용이 발생함을 뜻합니다.

Relax

이 좌측 밀집 제약을 완화해야 하지만, 이로 인해 두 가지 문제점이 발생합니다:

1. Radix 탐색은 노드의 분기수가 고정되어야 한다는 가정에 의존합니다.
2. 트리의 높이가 고정 분기수에 의해 제한되므로 거의 상수 시간 연산이 가능합니다.

첫 번째 문제는 노드의 실제 크기를 기록하면 해결할 수 있습니다. 각 브랜치 노드마다 size table(배열)을 추가해 노드의 자식 수만큼 크기를 기록합니다. 각 entry는 해당 slot(자식 노드)에 누적된 요소 개수를 저장합니다.

이 예에서 루트 노드는 두 자식이 있고, 사이즈 테이블을 보면 첫 번째 자식엔 14개, 두 번째엔 8개(22-14)가 들어있다는 것을 알 수 있습니다. 이렇게 각 slot이 포함하는 범위를 알면, 특정 인덱스의 요소를 찾는 방법은 다음과 같습니다:

1. 루트에서 시작해, 우리가 찾는 인덱스보다 큰 첫 번째 사이즈 테이블 entry가 있는 slot을 찾습니다. 예를 들어 인덱스 16을 찾을 때, 첫 slot은 건너뛰고(16>14), 두 번째 slot에서 찾습니다(16<22).
2. 이전 slot의 누적 크기를 인덱스에서 빼면 새 인덱스를 얻습니다(16-14=2).
3. slot을 따라 내려가며 같은 과정을 반복해서 결국 리프 노드에 닿으면 일반 배열 인덱싱으로 값을 찾습니다.

각 레벨에서 사이즈 테이블을 선형으로 스캔하면 radix indexing보다 작업이 많아지지만, 두 방식을 적절히 혼합하면 됩니다. 예를 들어 모든 slot이 M개 미만이어도, 현재 노드에 맞지 않는 경우는 이후 slot에 있으니, 먼저 radix로 찾고 그 후 많아야 2~3개 정도 slot을 추가로 확인하면 됩니다.

TypeScript로 구현 예시:

typescript
const M = 32 // 2의 거듭제곱
const BIT_WIDTH = Math.log2(M)

export const get = <T>(rrb: Rrb<T>, idx: number): T | null => {
  if (idx >= rrb.count) return null
  return findElement(rrb.root, idx)
}

const findElement = <T>(node: Node<T>, idx: number): T => {
  if (isBranch(node)) {
    const slot = findSlot(idx, node.height, node.sizes)
    const prevSize = slot === 0 ? 0 : node.sizes[slot - 1]
    const nextIdx = idx - prevSize
    return findElement(node.items[slot], nextIdx)
  } else {
    return node.items[idx]
  }
}

const findSlot = (idx: number, height: number, sizes: number[]): number => {
  let slot = idx >> (BIT_WIDTH * height)
  while (sizes[slot] <= idx) slot++
  return slot
}

최적화로, 좌측 밀집 노드에는 사이즈 테이블을 생략할 수 있습니다. 즉, Persistent Vector 방식에서 병합된 일부 노드에만 사이즈 테이블을 추가하면 되죠.

M..M-1 불변식 (Invariant)

트리의 높이 제한이 없어지는 두 번째 문제를 해결하기 위해 Persistent Vector에서처럼 모든 노드(우측엣지 제외)가 M개 slot을 갖는 대신, 각 노드는 M개 혹은 M-1개 slot을 갖는다는 불변식을 도입합니다(분기수가 4라면 각 노드는 3 또는 4개 slot, 실제로는 32라면 31~32개 slot).

분기수 32에서 트리의 최대 높이는 l o g₃₂(4,294,967,295) ≒ 6.39, 최악의 경우 l o g₃₁(4,294,967,295) ≒ 6.45, 즉 최대 7레벨로 제한됩니다.

이 불변식은 lookup 시 최대 몇 번 slot을 추가로 탐색해야 하는지도 제한합니다. 트리 높이가 h일 때, 최상위에서의 추가 탐색 횟수는 다음과 같이 구합니다:

(M^h - (M-1)^h) / M^{h-1}

예를 들어, 높이 5, 분기수 32인 경우 최악의 추가 탐색은 4.69회에 불과하지만, node 크기가 무작위라면 평균 2.49회의 추가 탐색만 하면 됩니다(사이즈 테이블이 작아 CPU 캐시에 잘 올라갑니다).

이로써 슬롯 수에 유연성을 두면서 효율적인 lookup을 유지할 수 있습니다. 두 벡터 병합 예로 돌아가 보겠습니다:

두 번째 리프 노드는 2개 slot만 있지만, 최소 3개 slot을 보장해야 하므로, 슬롯 재분배로 첫 노드의 마지막 slot이나 세 번째 노드의 첫 slot을 옮깁니다. 이렇게 2개의 새 노드만 생성하면 되니, Persistent Vector 방식에서 3개를 만드는 것보다 효율적입니다. 병합 시 오른쪽 벡터의 모든 요소를 왼쪽으로 옮길 필요 없이 전체 서브트리를 건드리지 않고도 병합할 수 있게 됩니다.

검색 단계(Search Step) 불변식

더 나은 방법도 있습니다. 위 예시에서 두 노드의 4개 슬롯을 새로운 4개 슬롯 노드로 합쳤는데, 만약 단순 병합만 했어도 각 인덱스의 추가 탐색 횟수(최대 1)는 동일합니다. 그렇다면 분기수 하한 대신, 추가 탐색 횟수에 불변식을 두는 게 더 나을 수 있습니다.

노드 P개를 최적으로 담으려면 ⌈P/M⌉개 슬롯이 필요합니다. 최대 E개 추가 탐색을 허용한다면, S ≤ ⌈P/M⌉+E 입니다. 이를 _검색 단계 불변식_이라 부릅니다. Bagwell & Rompf는 M=32, E=2일 때 인덱싱, 병합 성능 균형이 좋다고 합니다. (예시는 M=4, E=2)

이 불변식을 적용해 보면, 위 단순 병합에서도 4≤⌈14/4⌉+2=6, 즉 불변식이 만족되므로 재분배가 아예 필요없고 부모 노드만 새로 만들어주면 됩니다.

조금 더 복잡한 예로, 불균형 해소(rebalance) 알고리즘을 보면:

병합하는 두 노드의 총 슬롯을 모두 고려하고(S≤2M), 다음처럼 처리합니다:

1. 불변식 S≤⌈P/M⌉+E를 만족하지 않으면 진행
2. M-E/2개 이상 가진 slot은 건너뜀(재분배 필요 없음)
3. 부족한 slot의 아이템을 다음 братers에 분배 반복
4. 불변식 만족될 때까지 반복

실제 예로, 7≤⌈16/4⌉+2=6, 만족 안 하므로 2개 가진 slot을 셋째, 넷째 slot에 분배해 총 슬롯수를 줄여줍니다.

이 과정을 코드로 구현하면 다음과 같습니다:

typescript
const createConcatPlan = <T>(node: Branch<T>): number[] => {
  const plan = node.items.map(item => item.items.length)
  const s = plan.reduce((a, b) => a + b, 0)
  const opt = Math.ceil(s / M)

  let i = 0
  let n = plan.length
  while (n > opt + E_MAX) {
    while (plan[i] >= M - E_MAX / 2) i++
    let r = plan[i]
    while (r > 0) {
      plan[i] = Math.min(r + plan[i + 1], M)
      r = r + plan[i + 1] - plan[i]
      i += 1
    }
    for (let j = i; j < n - 1; j++) {
      plan[j] = plan[j + 1]
    }
    i--
    n--
  }
  return plan.slice(0, n)
}

병합(Merging)

마지막으로, 실제 트리 병합 과정을 봅시다!

사이즈 테이블은 생략합니다. 왼쪽 트리에서 가장 오른쪽 리프, 오른쪽 트리에서 가장 왼쪽 리프를 떼와 새 노드를 만들고, 이렇게 3개 노드(왼쪽, 중간, 오른쪽)가 생깁니다.

3개 노드의 슬롯을 모두 고려해, 검색 단계 불변식이 안 맞으면 재분배하고 새로운 부모 노드를 만듭니다. 오렌지색으로 표시된 새 노드가 생성되는 부분입니다. 이렇게 하면 기존 노드 대부분을 재사용해 작업량을 줄입니다.

생성된 부모 노드는 한 레벨 더 위에서 병합 반복, 좌우 노드의 끝 slot을 제외하고 세 노드의 슬롯을 합쳐 불변식 맞추면 됩니다.

이번에는 새로운 부모 노드가 한 개 slot만 가져서 트리의 레벨(높이)이 하나 추가됐는데, 불필요하므로 잘라줍니다.

이렇게 해서, 검색 단계 불변식을 유지하며 대부분 기존 노드를 재사용해 병합을 효율적으로 마쳤습니다.

구현 예시는 상당히 길지만 복잡하진 않습니다:

typescript
export const concat = <T>(left: Rrb<T>, right: Rrb<T>): Rrb<T> => {
  const merged = concatNodes(left.root, right.root)
  return {
    count: left.count + right.count,
    root:
      merged.items.length === 1 ? merged.items[0] : merged,
  }
}

const concatNodes = <T>(left: Node<T>, right: Node<T>, top: boolean = true): Branch<T> => {
  if (left.height > right.height) {
    assert(isBranch(left))
    const middle = concatNodes(array.last(left.items), right, false)
    return rebalance(left, middle, null, top)
  }
  if (left.height < right.height) {
    assert(isBranch(right))
    const middle = concatNodes(left, array.first(right.items), false)
    return rebalance(null, middle, right, top)
  }
  if (isLeaf(left) && isLeaf(right)) {
    const total = left.items.length + right.items.length
    if (top && total <= M) {
      return Branch(1, [Leaf([...left.items, ...right.items])])
    } else {
      return Branch(1, [left, right])
    }
  }
  if (isBranch(left) && isBranch(right)) {
    const middle = concatNodes(
      array.last(left.items),
      array.first(right.items),
      false
    )
    return rebalance(left, middle, right, top)
  }
  throw Error("unreachable")
}

const calcSizes = <T>(items: Node<T>[]): number[] => {
  let prev = 0
  return items.map(item => (prev += sizeOf(item)))
}

const rebalance = <T>(
  left: Branch<T> | null,
  middle: Branch<T>,
  right: Branch<T> | null,
  top: boolean
): Branch<T> => {
  const merged = Branch(middle.height, [
    ...(left ? array.init(left.items) : []),
    ...middle.items,
    ...(right ? array.tail(right.items) : []),
  ])
  const plan = createConcatPlan(merged)
  const balanced = executeConcatPlan(merged, plan)

  if (plan.length <= M) {
    return top ? balanced : Branch(balanced.height + 1, [balanced])
  } else {
    const left = Branch(balanced.height, balanced.items.slice(0, M))
    const right = Branch(balanced.height, balanced.items.slice(M))
    return Branch(balanced.height + 1, [left, right])
  }
}

const executeConcatPlan = <T>(node: Branch<T>, plan: number[]): Branch<T> => {
  const items: Node<T>[] = []
  let i = 0
  let offset = 0
  plan.forEach(target => {
    if (offset === 0 && node.items[i].items.length === target) {
      items.push(node.items[i])
      i += 1
    } else {
      const current: Node<T>[] | T[] = []
      while (current.length < target) {
        const required = target - current.length
        const size = node.items[i].items.length
        const available = size - offset
        const min = Math.min(required, available)
        current.push(
          ...(node.items[i].items.slice(offset, min + offset) as any)
        )
        if (min === available) {
          offset = 0
          i += 1
        } else {
          offset += min
        }
      }
      items.push(Node(node.height - 1, current))
    }
  })
  return Branch(node.height, items)
}

전체 예제 구현은 https://github.com/peterhorne/rrb-tree에서 볼 수 있습니다.