A simple B+Tree implementation.

pkg/analysis_server/lib/src/index/btree.dart

+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library index.btree;
+
+
+/**
+ * A simple B+Tree implementation.

[Brian Wilkerson, 2014/06/07 16:34:02]

"B+Tree" --> "B-Tree"

[scheglov, 2014/06/07 21:26:22]

It is actually not a mistake.
It is a B+Tree flavor of B-Tree.
The difference is that values are stored only in leaf nodes.
There are no references between leaf nodes, so it is not possible to do a range
scan, but in general I think it is still closer to B+Tree than to B-Tree.

[Brian Wilkerson, 2014/06/07 23:30:38]

Cool. I learned something new today. Interestingly enough I could only find one
reference in the first 5-6 pages of search results, so I might not be the only
one who didn't know about it. Perhaps a reference to the only article I could
find: http://en.wikipedia.org/wiki/B%2B_tree would be useful for others. (By the
way, they refer to it as a "B+ tree", even though the article on B-Tree's uses
"B-Tree". I don't know how standard that is, though.)

I would also suggest re-naming it "BPlusTree" so that it isn't confused with a
more traditional B-Tree implementation.

+ */
+class BTree<K, V> {
+  /**
+   * The [Comparator] to compare keys.
+   */
+  final Comparator<K> _comparator;
+
+  /**
+   * The maximum number of keys in an index node.
+   */
+  final int _maxIndexKeys;
+
+  /**
+   * The maximum number of keys in a leaf node.
+   */
+  final int _maxLeafKeys;
+
+  /**
+   * The root node.
+   */
+  _Node<K, V> _root;
+
+  BTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator) {
+    _root = new _LNode(_maxLeafKeys, _comparator);
+  }
+
+  /**
+   * Returns the value for [key] or `null` if [key] is not in the tree.
+   */
+  V find(K key) {
+    return _root.find(key);
+  }
+
+  /**
+   * Associates the [key] with the given [value].
+   *
+   * If the key was already in the tree, its associated value is changed.
+   * Otherwise the key-value pair is added to the tree.
+   */
+  void insert(K key, V value) {
+    _Split<K, V> result = _root.insert(key, value);
+    if (result != null) {
+      _INode<K, V> newRoot = new _INode<K, V>(_maxIndexKeys, _comparator);
+      newRoot.keys.add(result.key);
+      newRoot.children.add(result.left);
+      newRoot.children.add(result.right);
+      _root = newRoot;
+    }
+  }
+
+  noSuchMethod(Invocation invocation) {
+    if (invocation.memberName == #debugPrint) {

[Brian Wilkerson, 2014/06/07 16:34:02]

Why not just make debugPrint a public method? Doesn't this have the same effect
(other than hiding it from code completion)?

[scheglov, 2014/06/07 21:26:22]

OK, I think we can make it public again.

+      _debugPrint(invocation.positionalArguments[0]);
+      return null;
+    }
+    return super.noSuchMethod(invocation);
+  }
+
+  /**
+   * Removes the association for the given [key].
+   *
+   * Returns the value associated with [key] in the tree or `null` if [key] is
+   * not in the tree.
+   */
+  V remove(K key) {
+    _Remove<K, V> result = _root.remove(key, null, null, null);
+    if (_root is _INode<K, V>) {
+      List<_Node<K, V>> children = (_root as _INode<K, V>).children;
+      if (children.length == 1) {
+        _root = children[0];
+      }
+    }
+    return result.value;
+  }
+
+  /**
+   * Prints the debug presentation of the tree into [buffer].
+   */
+  void _debugPrint(StringBuffer buffer) {

[Brian Wilkerson, 2014/06/07 16:34:02]

Is there a reason why this isn't the implementation of toString? Assuming that
the debugger can use toString to display an object, it seems like this would be
a useful representation.

Either way you should rename it because it isn't (just) for debugging. Perhaps
something like "_writeOn".

[scheglov, 2014/06/07 21:26:22]

IMHO toString() is pretty dangerous to override for such potentially big and
slow data structure.
Done.

+    _root._debugPrint(buffer, '');
+  }
+}
+
+
+/**
+ * An index node with keys and children references.
+ */
+class _INode<K, V> extends _Node<K, V> {

[Brian Wilkerson, 2014/06/07 16:34:02]

I have a strong preference for using full names, such as "_IndexNode" and
"_LeafNode". Abbreviations are all too often confusing. Case in point: an inode,
is a data structure used to represent a filesystem object in Unix-based systems,
and that's what I think of every time I see this class name, even though that's
not what it is.

[scheglov, 2014/06/07 21:26:22]

Done.

+  final List<_Node<K, V>> children = new List<_Node<K, V>>();
+  final int maxKeys;
+  final int minKeys;
+
+  _INode(int maxKeys, Comparator<K> comparator)
+      : super(comparator),
+        maxKeys = maxKeys,
+        minKeys = maxKeys ~/ 2;
+
+  @override
+  V find(K key) {
+    int index = findChildIndex(key);
+    return children[index].find(key);
+  }
+
+  /**
+   * Returns the index of the child into which [key] should be inserted.
+   */
+  int findChildIndex(K key) {
+    for (int i = 0; i < keys.length; i++) {
+      if (comparator(keys[i], key) > 0) {
+        return i;
+      }
+    }
+    return keys.length;
+  }
+
+  _Split insert(K key, V value) {

[Brian Wilkerson, 2014/06/07 16:34:02]

"_Split" --> "_Split<K, V>"

[scheglov, 2014/06/07 21:26:22]

Done.

+    // Early split.
+    if (keys.length == maxKeys) {
+      int middle = (maxKeys + 1) ~/ 2;
+      K splitKey = keys[middle];
+      _INode<K, V> sibling = new _INode<K, V>(maxKeys, comparator);
+      sibling.keys.addAll(keys.getRange(middle + 1, keys.length));
+      sibling.children.addAll(children.getRange(middle + 1, children.length));
+      keys.length = middle;
+      children.length = middle + 1;
+      // Prepare split.
+      _Split<K, V> result = new _Split<K, V>(splitKey, this, sibling);
+      if (comparator(key, result.key) < 0) {
+        insertNotFull(key, value);
+      } else {
+        sibling.insertNotFull(key, value);
+      }
+      return result;
+    }
+    // No split.
+    insertNotFull(key, value);
+    return null;
+  }
+
+  void insertNotFull(K key, V value) {
+    int index = findChildIndex(key);
+    _Split<K, V> result = children[index].insert(key, value);
+    if (result != null) {
+      keys.insert(index, result.key);
+      children[index] = result.left;
+      children.insert(index + 1, result.right);
+    }
+  }
+
+  @override
+  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) {
+    int index = findChildIndex(key);
+    K thisAnchor = index == 0 ? keys[0] : keys[index - 1];
+    _Node<K, V> child = children[index];
+    bool hasLeft = index != 0;
+    bool hasRight = index < children.length - 1;
+    _Node<K, V> leftChild = hasLeft ? children[index - 1] : null;
+    _Node<K, V> rightChild = hasRight ? children[index + 1] : null;
+    // Ask child to remove.
+    _Remove<K, V> result = child.remove(key, leftChild, thisAnchor, rightChild);
+    V value = result.value;
+    if (value == null) {
+      return new _Remove<K, V>(value);
+    }
+    // Update anchor if borrowed.
+    if (result.leftAnchor != null) {
+      keys[index - 1] = result.leftAnchor;
+    }
+    if (result.rightAnchor != null) {
+      keys[index] = result.rightAnchor;
+    }
+    // Update keys / children if merged.
+    if (result.mergedLeft) {
+      keys.removeAt(index - 1);
+      children.removeAt(index);
+    }
+    if (result.mergedRight) {
+      keys.removeAt(index);
+      children.removeAt(index);
+    }
+    // Perform balancing.
+    if (keys.length < minKeys) {
+      // Try left sibling.
+      if (left is _INode<K, V>) {
+        // Try to redistribute.
+        int leftLength = left.keys.length;
+        if (leftLength > minKeys) {
+          int halfExcess = (leftLength - minKeys + 1) ~/ 2;
+          int newLeftLength = leftLength - halfExcess;
+          keys.insert(0, anchor);
+          keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength));
+          children.insertAll(0, left.children.getRange(newLeftLength, leftLength
+              + 1));
+          K newAnchor = left.keys[newLeftLength - 1];
+          left.keys.length = newLeftLength - 1;
+          left.children.length = newLeftLength;
+          return new _Remove<K, V>.borrowLeft(value, newAnchor);
+        }
+        // Do merge.
+        left.keys.add(anchor);
+        left.keys.addAll(keys);
+        left.children.addAll(children);
+        return new _Remove<K, V>.mergeLeft(value);
+      }
+      // Try right sibling.
+      if (right is _INode<K, V>) {
+        // Try to redistribute.
+        var rightLength = right.keys.length;
+        if (rightLength > minKeys) {
+          int halfExcess = (rightLength - minKeys + 1) ~/ 2;
+          keys.add(anchor);
+          keys.addAll(right.keys.getRange(0, halfExcess - 1));
+          children.addAll(right.children.getRange(0, halfExcess));
+          K newAnchor = right.keys[halfExcess - 1];
+          right.keys.removeRange(0, halfExcess);
+          right.children.removeRange(0, halfExcess);
+          return new _Remove<K, V>.borrowRight(value, newAnchor);
+        }
+        // Do merge.
+        right.keys.insert(0, anchor);
+        right.keys.insertAll(0, keys);
+        right.children.insertAll(0, children);
+        return new _Remove<K, V>.mergeRight(value);
+      }
+    }
+    // No balancing required.
+    return new _Remove<K, V>(value);
+  }
+
+  @override
+  void _debugPrint(StringBuffer buffer, String indent) {
+    buffer.write(indent);
+    buffer.write('INode {\n');
+    for (int i = 0; i < keys.length; i++) {
+      children[i]._debugPrint(buffer, indent + '    ');
+      buffer.write(indent);
+      buffer.write('  ');
+      buffer.write(keys[i]);
+      buffer.write('\n');
+    }
+    children[keys.length]._debugPrint(buffer, indent + '    ');
+    buffer.write(indent);
+    buffer.write('}\n');
+  }
+}
+
+
+/**
+ * A leaf node with keys and values.
+ */
+class _LNode<K, V> extends _Node<K, V> {
+  final int maxKeys;
+  final int minKeys;
+
+  /**
+   *  The list of values.
+   */
+  final List<V> values = new List<V>();
+
+  _LNode(int maxKeys, Comparator<K> comparator)
+      : super(comparator),
+        maxKeys = maxKeys,
+        minKeys = maxKeys ~/ 2;
+
+  @override
+  V find(K key) {
+    int index = findKeyIndex(key);
+    if (index < 0) {
+      return null;
+    }
+    if (index >= keys.length) {
+      return null;
+    }
+    if (keys[index] != key) {
+      return null;
+    }
+    return values[index];
+  }
+
+  /**
+   * Returns the index where [key] should be inserted.
+   */
+  int findKeyIndex(K key) {
+    for (int i = 0; i < keys.length; i++) {
+      if (comparator(keys[i], key) >= 0) {
+        return i;
+      }
+    }
+    return keys.length;
+  }
+
+  _Split<K, V> insert(K key, V value) {
+    int index = findKeyIndex(key);
+    // The node is full.
+    if (keys.length == maxKeys) {
+      int middle = (maxKeys + 1) ~/ 2;
+      _LNode<K, V> sibling = new _LNode<K, V>(maxKeys, comparator);
+      sibling.keys.addAll(keys.getRange(middle, keys.length));
+      sibling.values.addAll(values.getRange(middle, values.length));
+      keys.length = middle;
+      values.length = middle;
+      // Insert into the left / right sibling.
+      if (index < middle) {
+        insertNotFull(key, value, index);
+      } else {
+        sibling.insertNotFull(key, value, index - middle);
+      }
+      // Notify the parent about the split.
+      return new _Split<K, V>(sibling.keys[0], this, sibling);
+    }
+    // The node was not full.
+    insertNotFull(key, value, index);
+    return null;
+  }
+
+  void insertNotFull(K key, V value, int index) {
+    if (index < keys.length && keys[index] == key) {
+      values[index] = value;
+    } else {
+      keys.insert(index, key);
+      values.insert(index, value);
+    }
+  }
+
+  @override
+  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) {
+    // Find the key.
+    int index = keys.indexOf(key);
+    if (index == -1) {
+      return new _Remove<K, V>(null);
+    }
+    // Key key / value.
+    keys.removeAt(index);
+    V value = values.removeAt(index);
+    // Perform balancing.
+    if (keys.length < minKeys) {
+      // Try left sibling.
+      if (left is _LNode<K, V>) {
+        // Try to redistribute.
+        int leftLength = left.keys.length;
+        if (leftLength > minKeys) {
+          int halfExcess = (leftLength - minKeys + 1) ~/ 2;
+          int newLeftLength = leftLength - halfExcess;
+          keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength));
+          values.insertAll(0, left.values.getRange(newLeftLength, leftLength));
+          left.keys.length = newLeftLength;
+          left.values.length = newLeftLength;
+          return new _Remove<K, V>.borrowLeft(value, keys.first);
+        }
+        // Do merge.
+        left.keys.addAll(keys);
+        left.values.addAll(values);
+        return new _Remove<K, V>.mergeLeft(value);
+      }
+      // Try right sibling.
+      if (right is _LNode<K, V>) {
+        // Try to redistribute.
+        var rightLength = right.keys.length;
+        if (rightLength > minKeys) {
+          int halfExcess = (rightLength - minKeys + 1) ~/ 2;
+          keys.addAll(right.keys.getRange(0, halfExcess));
+          values.addAll(right.values.getRange(0, halfExcess));
+          right.keys.removeRange(0, halfExcess);
+          right.values.removeRange(0, halfExcess);
+          return new _Remove<K, V>.borrowRight(value, right.keys.first);
+        }
+        // Do merge.
+        right.keys.insertAll(0, keys);
+        right.values.insertAll(0, values);
+        return new _Remove<K, V>.mergeRight(value);
+      }
+    }
+    // No balancing required.
+    return new _Remove<K, V>(value);
+  }
+
+  @override
+  void _debugPrint(StringBuffer buffer, String indent) {
+    buffer.write(indent);
+    buffer.write('LNode {');
+    for (int i = 0; i < keys.length; i++) {
+      if (i != 0) {
+        buffer.write(', ');
+      }
+      buffer.write(keys[i]);
+      buffer.write(': ');
+      buffer.write(values[i]);
+    }
+    buffer.write('}\n');
+  }
+}
+
+
+/**
+ * An internal or leaf node.
+ */
+abstract class _Node<K, V> {

[Brian Wilkerson, 2014/06/07 16:34:02]

It is easier for me to read the code in a Dart file (at least in a plain text
editor/viewer) if superclasses come before subclasses. I know that goes against
what we discussed for the sorter, so I'm not asking for a change, just making an
observation.

[scheglov, 2014/06/07 21:26:22]

I agree.
And there is another problem with sorting fields - sometimes one would like to
organize them in a logical grouping - like leaf/right references together,
offset/length instead of length/offset alphabetical order. But that's the price
you pay for an auto-organizing - everything is organized consistently, but not
always in the best form.

+  /**
+   * The [Comparator] to compare keys.
+   */
+  Comparator<K> comparator;
+
+  /**
+   *  The list of keys.
+   */
+  List<K> keys = new List<K>();
+
+  _Node(this.comparator);
+
+  /**
+   * Looks for [key].
+   *
+   * Returns the associated value if found.
+   * Returns `null` if not found.
+   */
+  V find(K key);
+
+  /**
+   * Inserts the [key] / [value] pair into this [_Node].
+   *
+   * Returns a [_Split] object if split happens, or `null` otherwise.
+   */
+  _Split<K, V> insert(K key, V value);
+
+  /**
+   * Removes the association for the given [key].
+   *
+   * Returns the [_Remove] information about an operation performed.
+   * It may be restructuring or merging, with [left] or [left] siblings.
+   */
+  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right);
+
+  /**
+   * Prints the debug presentation of the node into [buffer].
+   */
+  void _debugPrint(StringBuffer buffer, String indent);
+}
+
+
+/**
+ * A container with information about redistribute / merge.
+ */
+class _Remove<K, V> {
+  K leftAnchor;
+  bool mergedLeft = false;
+  bool mergedRight = false;
+  K rightAnchor;
+  final V value;
+  _Remove(this.value);
+  _Remove.borrowLeft(this.value, this.leftAnchor);
+  _Remove.borrowRight(this.value, this.rightAnchor);
+  _Remove.mergeLeft(this.value) : mergedLeft = true;
+  _Remove.mergeRight(this.value) : mergedRight = true;
+}
+
+
+/**
+ * A container with information about split during insert.
+ */
+class _Split<K, V> {
+  final K key;
+  final _Node<K, V> left;
+  final _Node<K, V> right;
+  _Split(this.key, this.left, this.right);
+}