資料結構

1class BNode {
2  keys: number[] = [];
3  children: BNode[] = [];
4}
5 
6type Split = { median: number; right: BNode };
7 
8class BTree {
9  root = new BNode();
10  constructor(private maxKeys: number) {}
11 
12  search(key: number): boolean {
13    let node = this.root;
14    while (true) {
15      let i = 0;
16      while (i < node.keys.length && key > node.keys[i]) i++;
17      if (node.keys[i] === key) return true;
18      if (node.children.length === 0) return false;
19      node = node.children[i];
20    }
21  }
22 
23  insert(key: number): void {
24    const split = this.insertAt(this.root, key);
25    if (split) {
26      const root = new BNode();
27      root.keys = [split.median];
28      root.children = [this.root, split.right];
29      this.root = root;
30    }
31  }
32 
33  private insertAt(node: BNode, key: number): Split | null {
34    let i = 0;
35    while (i < node.keys.length && key > node.keys[i]) i++;
36    if (node.keys[i] === key) return null;
37    if (node.children.length === 0) {
38      node.keys.splice(i, 0, key);
39    } else {
40      const split = this.insertAt(node.children[i], key);
41      if (!split) return null;
42      node.keys.splice(i, 0, split.median);
43      node.children.splice(i + 1, 0, split.right);
44    }
45    if (node.keys.length <= this.maxKeys) return null;
46    const mid = Math.floor(node.keys.length / 2);
47    const right = new BNode();
48    right.keys = node.keys.splice(mid + 1);
49    if (node.children.length) right.children = node.children.splice(mid + 1);
50    return { median: node.keys.pop()!, right };
51  }
52 
53  // In-order walk of only the subtrees that can hold keys in [lo, hi].
54  rangeScan(lo: number, hi: number): number[] {
55    const out: number[] = [];
56    const visit = (node: BNode): boolean => {                  // false once past hi
57      const k = node.keys.length;
58      for (let i = 0; i <= k; i++) {
59        const above = i === 0 ? -Infinity : node.keys[i - 1];
60        const below = i === k ? Infinity : node.keys[i];
61        if (node.children.length && lo < below && above < hi) {
62          if (!visit(node.children[i])) return false;
63        }
64        if (i === k) break;
65        if (node.keys[i] > hi) return false;
66        if (node.keys[i] >= lo) out.push(node.keys[i]);
67      }
68      return true;
69    };
70    visit(this.root);
71    return out;
72  }
73}
74 
75// B+ tree: every key lives in a leaf, and the leaves are linked.
76class BPNode {
77  keys: number[] = [];
78  children: BPNode[] = [];
79  next: BPNode | null = null;
80}
81 
82class BPlusTree {
83  root = new BPNode();
84  constructor(private maxKeys: number) {}
85 
86  insert(key: number): void {
87    const path: Array<[BPNode, number]> = [];
88    let node = this.root;
89    while (node.children.length) {
90      let i = 0;
91      while (i < node.keys.length && key >= node.keys[i]) i++;
92      path.push([node, i]);
93      node = node.children[i];
94    }
95    let at = 0;
96    while (at < node.keys.length && node.keys[at] < key) at++;
97    if (node.keys[at] === key) return;
98    node.keys.splice(at, 0, key);
99    if (node.keys.length <= this.maxKeys) return;
100    const right = new BPNode();
101    right.keys = node.keys.splice(Math.floor(node.keys.length / 2));
102    right.next = node.next;
103    node.next = right;
104    let separator = right.keys[0];                             // copied up; it stays in the leaf
105    let left = node;
106    let newChild = right;
107    while (path.length) {
108      const [parent, i] = path.pop()!;
109      parent.keys.splice(i, 0, separator);
110      parent.children.splice(i + 1, 0, newChild);
111      if (parent.keys.length <= this.maxKeys) return;
112      const mid = Math.floor(parent.keys.length / 2);
113      const sibling = new BPNode();
114      sibling.keys = parent.keys.splice(mid + 1);
115      sibling.children = parent.children.splice(mid + 1);
116      separator = parent.keys.pop()!;                          // moved up, as in a B-tree
117      left = parent;
118      newChild = sibling;
119    }
120    const root = new BPNode();
121    root.keys = [separator];
122    root.children = [left, newChild];
123    this.root = root;
124  }
125 
126  // Down once to the leaf holding lo, then along the leaf chain.
127  rangeScan(lo: number, hi: number): number[] {
128    let node = this.root;
129    while (node.children.length) {
130      let i = 0;
131      while (i < node.keys.length && lo >= node.keys[i]) i++;
132      node = node.children[i];
133    }
134    const out: number[] = [];
135    for (let leaf: BPNode | null = node; leaf; leaf = leaf.next) {
136      for (const key of leaf.keys) {
137        if (key > hi) return out;
138        if (key >= lo) out.push(key);
139      }
140    }
141    return out;
142  }
143}