B - tree

• 이진 트리를 확장해서 노드가 가질 수 있는 값이 2 이상이고, 가질 수 있는 자식의 노드 숫자도 2이상인 트리 구조.

• B-트리의 기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능.

• 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 혹은 다른 노드와 합쳐지게 된다.

• 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 합침을 통한 재균형 과정은 다른 자가 균형 이진 탐색 트리만큼 자주 일어나지 않지만, 저장 공간에서의 손실은 있게 된다.

• 삽입 및 삭제를 대수시간(log n)으로 할 수 있다.

• 조건

  1. 노드의 자료의 값들은 정렬되어야 한다.
  2. 노드의 자료수가 K면, 자식의 수는 K + 1 이여야 함.
  3. 한 노드 자료보다 왼쪽 서브트리는 노드보다 작은 키값, 오른쪽은 큰값.
  4. 루트 노드를 제외한 모든 노드는 적어도 M/2(소수점 내림)의 키를 가지고 있어야 한다. (M은 차수)
  5. 리프 노드는 같은 레벨

• B tree의 B는 무엇인가?

  • B-트리의 창시자인 루돌프 바이어는 'B'가 무엇을 의미하는지 따로 언급하지는 않았다. 가장 가능성 있는 대답은 리프 노드를 같은 높이에서 유지시켜주므로 균형잡혀있다(balanced)는 뜻에서의 'B'라는 것이다. '바이어(Bayer)'의 'B'를 나타낸다는 의견도, 혹은 그가 일했던 보잉 과학 연구소(Boeing Scientific Research Labs)에서의 'B'를 나타낸다는 의견도 있다.
  • Balanced가 유력하지 않을까 생각한다.

• 삽입 구현

  • 리프노드에 값을 추가해줘야하므로 리프노드를 찾아야한다.
  • 트리의 차수에 맞춰서 data를 가져야하고, 차수랑 같은 값을 가지는 경우 분할해줘야한다.
    • 분할 해주는 과정에서 루트인 경우와 부모를 가지는 경우를 나눠서 분할한다.

class B {
  constructor(m, parent, datas, trees, leaf = true) {
    this.m = m; // 트리의 차수
    this.parent = parent ? parent : null;
    this.datas = datas ? datas : [];
    this.trees = trees ? trees : [];
    this.leaf = leaf;
  }

  add(value) {
    // 리프노드가 아닌 경우는 해당 값을 넣을 트리를 찾아야한다.
    if (!this.leaf) {
      const treeIndex = this.datas.findIndex((data) => value <= data);
      const dataIdx = treeIndex < 0 ? this.datas.length : treeIndex;
      this.trees[dataIdx].add(value);
    } else {
      this.datas.push(value);
      this.datas.sort((a, b) => a - b);
    }

    // 트리가 가질 수 있는 데이터가 꽉찬 경우
    if (this.datas.length === this.m) {
      // root인 경우 - 루트인 경우에는 m/2의 값을 기준으로 트리를 새로 만들어주면 된다.
      if (this.parent === null) {
        const pivot = this.m % 2 === 0 ? this.m / 2 : parseInt(this.m / 2);
        const { leftB_tree, rightB_tree } = this.split(pivot, this);
        this.datas = [this.datas[pivot]];
        this.trees = [leftB_tree, rightB_tree];
        this.leaf = false;
        return;
      }

      //root가 아닌 경우(부모가 있는 경우) - m/2 값을 부모의 데이터에 추가하고, 나눠진 tree는 부모의 trees에 추가해줘야한다.
      const pivot = this.m % 2 === 0 ? this.m / 2 - 1 : parseInt(this.m / 2);
      const target = this.datas[pivot]; // 나눠지는 값
      const parent = this.parent;
      parent.datas.push(target);
      parent.datas.sort((a, b) => a - b);
      const idx = parent.datas.findIndex((data) => target === data);
      const parentRestTrees = parent.datas.slice(idx + 1); // target이 추가되는 자리에 존재했던 tree들
      const { leftB_tree, rightB_tree } = this.split(pivot, parent);
      parent.trees[idx] = leftB_tree;
      parent.trees[idx + 1] = rightB_tree;
      parent.trees = parent.trees.concat(parentRestTrees);
      parent.leaf = false;
      return;
    }
    return;
  }

  split(pivot, parent) {
    const leftDatas = this.datas.slice(0, pivot);
    const rightDatas = this.datas.slice(pivot + 1);
    const leftTrees = this.trees.slice(0, pivot + 1);
    const rightTrees = this.trees.slice(pivot + 1);
    const isLeaf = leftTrees.length > 0 ? false : true;
    const leftB_tree = new B(this.m, parent, leftDatas, leftTrees, isLeaf);
    const rightB_tree = new B(this.m, parent, rightDatas, rightTrees, isLeaf);
    return { leftB_tree, rightB_tree };
  }
}

참고

https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html

https://matice.tistory.com/8

https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC

https://www.cs.usfca.edu/~galles/visualization/BTree.html(작동을 잘 볼 수 있어서 구현하는데 있어서 많은 힌트를 얻음.)