Create/read/write/delete nodes using NodeManager.

pkg/analysis_server/lib/src/index/b_plus_tree.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.b_plus_tree;
 
+import 'dart:collection';
+
 
 /**
  * A simple B+ tree (http://en.wikipedia.org/wiki/B+_tree) implementation.
+ *
+ * [K] is the keys type.
+ * [V] is the values type.
+ * [N] is the type of node identifiers using by the [NodeManager].
  */
-class BPlusTree<K, V> {
+class BPlusTree<K, V, N> {
   /**
    * The [Comparator] to compare keys.
    */
   final Comparator<K> _comparator;
 
   /**
+   * The [NodeManager] to manage nodes.
+   */
+  final NodeManager<K, V, N> _manager;
+
+  /**
    * 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;
+  _Node<K, V, N> _root;
 
-  BPlusTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator) {
-    _root = new _LeafNode(_maxLeafKeys, _comparator);
+  /**
+   * Creates a new [BPlusTree] instance.
+   */
+  BPlusTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator,
+      this._manager) {
+    _root = _newLeafNode();
+    _writeLeafNode(_root);
   }
 
   /**
    * 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);
+    _Split<K, N> result = _root.insert(key, value);
     if (result != null) {
-      _IndexNode<K, V> newRoot = new _IndexNode<K, V>(_maxIndexKeys,
-          _comparator);
+      _IndexNode<K, V, N> newRoot = _newIndexNode();
       newRoot.keys.add(result.key);
       newRoot.children.add(result.left);
       newRoot.children.add(result.right);
       _root = newRoot;
+      _writeIndexNode(_root);
     }
   }
 
   /**
    * 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 _IndexNode<K, V>) {
-      List<_Node<K, V>> children = (_root as _IndexNode<K, V>).children;
+    if (_root is _IndexNode<K, V, N>) {
+      List<N> children = (_root as _IndexNode<K, V, N>).children;
       if (children.length == 1) {
-        _root = children[0];
+        _manager.delete(_root.id);
+        _root = _readNode(children[0]);
       }
     }
     return result.value;
   }
 
   /**
    * Writes a textual presentation of the tree into [buffer].
    */
   void writeOn(StringBuffer buffer) {
     _root.writeOn(buffer, '');
   }
+
+  /**
+   * Creates a new [_IndexNode] instance.
+   */
+  _IndexNode<K, V, N> _newIndexNode() {
+    N id = _manager.createIndex();
+    return new _IndexNode<K, V, N>(this, id, _maxIndexKeys);
+  }
+
+  /**
+   * Creates a new [_LeafNode] instance.
+   */
+  _LeafNode<K, V, N> _newLeafNode() {
+    N id = _manager.createLeaf();
+    return new _LeafNode<K, V, N>(this, id, _maxLeafKeys);
+  }
+
+  /**
+   * Reads the [_IndexNode] with [id] from the manager.
+   */
+  _IndexNode<K, V, N> _readIndexNode(N id) {
+    IndexNodeData<K, N> data = _manager.readIndex(id);
+    _IndexNode<K, V, N> node = new _IndexNode<K, V, N>(this, id, _maxIndexKeys);
+    node.keys.addAll(data.keys);
+    node.children.addAll(data.children);
+    return node;
+  }
+
+  /**
+   * Reads the [_LeafNode] with [id] from the manager.
+   */
+  _LeafNode<K, V, N> _readLeafNode(N id) {
+    _LeafNode<K, V, N> node = new _LeafNode<K, V, N>(this, id, _maxLeafKeys);
+    LeafNodeData<K, V> data = _manager.readLeaf(id);
+    node.keys.addAll(data.keys);
+    node.values.addAll(data.values);
+    return node;
+  }
+
+  /**
+   * Reads the [_IndexNode] or [_LeafNode] with [id] from the manager.
+   */
+  _Node<K, V, N> _readNode(N id) {
+    if (_manager.isIndex(id)) {
+      return _readIndexNode(id);
+    } else {
+      return _readLeafNode(id);
+    }
+  }
+
+  /**
+   * Writes [node] into the manager.
+   */
+  void _writeIndexNode(_IndexNode<K, V, N> node) {
+    _manager.writeIndex(node.id, new IndexNodeData(node.keys, node.children));
+  }
+
+  /**
+   * Writes [node] into the manager.
+   */
+  void _writeLeafNode(_LeafNode<K, V, N> node) {
+    _manager.writeLeaf(node.id, new LeafNodeData(node.keys, node.values));
+  }
+}
+
+
+/**
+ * A container with information about an index node.
+ */
+class IndexNodeData<K, N> {
+  final List<N> children;
+  final List<K> keys;
+  IndexNodeData(this.keys, this.children);
+}
+
+
+/**
+ * A container with information about a leaf node.
+ */
+class LeafNodeData<K, V> {
+  final List<K> keys;
+  final List<V> values;
+  LeafNodeData(this.keys, this.values);
+}
+
+
+/**
+ * An implementation of [NodeManager] that keeps node information in memory.
+ */
+class MemoryNodeManager<K, V> implements NodeManager<K, V, int> {
+  Map<int, IndexNodeData> _indexDataMap = new HashMap<int, IndexNodeData>();
+  Map<int, LeafNodeData> _leafDataMap = new HashMap<int, LeafNodeData>();
+  int _nextPageIndexId = 0;
+  int _nextPageLeafId = 1;
+
+  @override
+  int createIndex() {
+    int id = _nextPageIndexId;
+    _nextPageIndexId += 2;
+    return id;
+  }
+
+  @override
+  int createLeaf() {
+    int id = _nextPageLeafId;
+    _nextPageLeafId += 2;
+    return id;
+  }
+
+  @override
+  void delete(int id) {
+    if (isIndex(id)) {
+      _indexDataMap.remove(id);
+    } else {
+      _leafDataMap.remove(id);
+    }
+  }
+
+  @override
+  bool isIndex(int id) {
+    return id.isEven;
+  }
+
+  @override
+  IndexNodeData<K, int> readIndex(int id) {
+    return _indexDataMap[id];
+  }
+
+  @override
+  LeafNodeData<K, V> readLeaf(int id) {
+    return _leafDataMap[id];
+  }
+
+  @override
+  void writeIndex(int id, IndexNodeData<K, V> data) {
+    _indexDataMap[id] = data;
+  }
+
+  @override
+  void writeLeaf(int id, LeafNodeData<K, V> data) {
+    _leafDataMap[id] = data;
+  }
+}
+
+
+/**
+ * A manager that manages nodes.
+ */
+abstract class NodeManager<K, V, N> {
+  /**
+   * Generates an identifier for a new index node.
+   */
+  N createIndex();
+
+  /**
+   * Generates an identifier for a new leaf node.
+   */
+  N createLeaf();
+
+  /**
+   * Deletes the node with the given identifier.
+   */
+  void delete(N id);
+
+  /**
+   * Checks if the node with the given identifier is an index or a leaf node.
+   */
+  bool isIndex(N id);
+
+  /**
+   * Reads information about the index node with the given identifier.
+   */
+  IndexNodeData<K, N> readIndex(N id);
+
+  /**
+   * Reads information about the leaf node with the given identifier.
+   */
+  LeafNodeData<K, V> readLeaf(N id);
+
+  /**
+   * Writes information about the index node with the given identifier.
+   */
+  void writeIndex(N id, IndexNodeData<K, V> data);
+
+  /**
+   * Writes information about the leaf node with the given identifier.
+   */
+  void writeLeaf(N id, LeafNodeData<K, V> data);
 }
 
 
 /**
  * An index node with keys and children references.
  */
-class _IndexNode<K, V> extends _Node<K, V> {
-  final List<_Node<K, V>> children = new List<_Node<K, V>>();
+class _IndexNode<K, V, N> extends _Node<K, V, N> {

[Brian Wilkerson, 2014/06/08 16:50:06]

Should "_IndexNode" be renamed (in a separate CL) to "_InternalNode" to reflect
what little literature there appears to be about this data structure and to make
it more generic?

+  final List<N> children = new List<N>();
   final int maxKeys;
   final int minKeys;
 
-  _IndexNode(int maxKeys, Comparator<K> comparator)
-      : super(comparator),
+  _IndexNode(BPlusTree<K, V, N> tree, N id, int maxKeys)
+      : super(tree, id),
         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<K, V> insert(K key, V value) {
+    int index = _findChildIndex(key);
+    _Node<K, V, N> child = tree._readNode(children[index]);
+    return child.find(key);
+  }
+
+  _Split<K, N> insert(K key, V value) {
     // Early split.
     if (keys.length == maxKeys) {
       int middle = (maxKeys + 1) ~/ 2;
       K splitKey = keys[middle];
-      _IndexNode<K, V> sibling = new _IndexNode<K, V>(maxKeys, comparator);
+      // Overflow into a new sibling.
+      _IndexNode<K, V, N> sibling = tree._newIndexNode();
       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;
+      // Insert into this node or sibling.
+      if (comparator(key, splitKey) < 0) {
+        _insertNotFull(key, value);
+      } else {
+        sibling._insertNotFull(key, value);
+      }
       // 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;
+      tree._writeIndexNode(this);
+      tree._writeIndexNode(sibling);
+      return new _Split<K, N>(splitKey, id, sibling.id);
     }
     // No split.
-    insertNotFull(key, value);
+    _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);
+  @override
+  _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V,
+      N> 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;
+    // Prepare children.
+    _Node<K, V, N> child = tree._readNode(children[index]);
+    _Node<K, V, N> leftChild;
+    _Node<K, V, N> rightChild;
+    if (index != 0) {
+      leftChild = tree._readNode(children[index - 1]);
+    } else {
+      leftChild = null;
+    }
+    if (index < children.length - 1) {
+      rightChild = tree._readNode(children[index + 1]);
+    } else {
+      rightChild = 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);
-    }
+    // Do keys / children updates
+    bool hasUpdates = false;
+    {
+      // Update anchor if borrowed.
+      if (result.leftAnchor != null) {
+        keys[index - 1] = result.leftAnchor;
+        hasUpdates = true;
+      }
+      if (result.rightAnchor != null) {
+        keys[index] = result.rightAnchor;
+        hasUpdates = true;
+      }
+      // Update keys / children if merged.
+      if (result.mergedLeft) {
+        keys.removeAt(index - 1);
+        N child = children.removeAt(index);
+        manager.delete(child);
+        hasUpdates = true;
+      }
+      if (result.mergedRight) {
+        keys.removeAt(index);
+        N child = children.removeAt(index);
+        manager.delete(child);
+        hasUpdates = true;
+      }
+    }
+    // Write if updated.
+    if (!hasUpdates) {
+      return new _Remove<K, V>(value);
+    }
+    tree._writeIndexNode(this);
     // Perform balancing.
     if (keys.length < minKeys) {
       // Try left sibling.
-      if (left is _IndexNode<K, V>) {
+      if (left is _IndexNode<K, V, N>) {
         // 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;
+          tree._writeIndexNode(this);
+          tree._writeIndexNode(left);
           return new _Remove<K, V>.borrowLeft(value, newAnchor);
         }
         // Do merge.
         left.keys.add(anchor);
         left.keys.addAll(keys);
         left.children.addAll(children);
+        tree._writeIndexNode(this);
+        tree._writeIndexNode(left);
         return new _Remove<K, V>.mergeLeft(value);
       }
       // Try right sibling.
-      if (right is _IndexNode<K, V>) {
+      if (right is _IndexNode<K, V, N>) {
         // 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);
+          tree._writeIndexNode(this);
+          tree._writeIndexNode(right);
           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);
+        tree._writeIndexNode(this);
+        tree._writeIndexNode(right);
         return new _Remove<K, V>.mergeRight(value);
       }
     }
     // No balancing required.
     return new _Remove<K, V>(value);
   }
 
   @override
   void writeOn(StringBuffer buffer, String indent) {
     buffer.write(indent);
     buffer.write('INode {\n');
     for (int i = 0; i < keys.length; i++) {
-      children[i].writeOn(buffer, indent + '    ');
+      _Node<K, V, N> child = tree._readNode(children[i]);
+      child.writeOn(buffer, indent + '    ');
       buffer.write(indent);
       buffer.write('  ');
       buffer.write(keys[i]);
       buffer.write('\n');
     }
-    children[keys.length].writeOn(buffer, indent + '    ');
+    _Node<K, V, N> child = tree._readNode(children[keys.length]);
+    child.writeOn(buffer, indent + '    ');
     buffer.write(indent);
     buffer.write('}\n');
   }
+
+  /**
+   * 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;
+  }
+
+  void _insertNotFull(K key, V value) {
+    int index = _findChildIndex(key);
+    _Node<K, V, N> child = tree._readNode(children[index]);
+    _Split<K, N> result = child.insert(key, value);
+    if (result != null) {
+      keys.insert(index, result.key);
+      children[index] = result.left;
+      children.insert(index + 1, result.right);
+      tree._writeIndexNode(this);
+    }
+  }
 }
 
 
 /**
  * A leaf node with keys and values.
  */
-class _LeafNode<K, V> extends _Node<K, V> {
+class _LeafNode<K, V, N> extends _Node<K, V, N> {
   final int maxKeys;
   final int minKeys;
-
-  /**
-   *  The list of values.
-   */
   final List<V> values = new List<V>();
 
-  _LeafNode(int maxKeys, Comparator<K> comparator)
-      : super(comparator),
+  _LeafNode(BPlusTree<K, V, N> tree, N id, int maxKeys)
+      : super(tree, id),
         maxKeys = maxKeys,
         minKeys = maxKeys ~/ 2;
 
   @override
   V find(K key) {
-    int index = findKeyIndex(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);
+  _Split<K, N> insert(K key, V value) {
+    int index = _findKeyIndex(key);
     // The node is full.
     if (keys.length == maxKeys) {
       int middle = (maxKeys + 1) ~/ 2;
-      _LeafNode<K, V> sibling = new _LeafNode<K, V>(maxKeys, comparator);
+      _LeafNode<K, V, N> sibling = tree._newLeafNode();
       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);
+        _insertNotFull(key, value, index);
       } else {
-        sibling.insertNotFull(key, value, index - middle);
+        sibling._insertNotFull(key, value, index - middle);
       }
       // Notify the parent about the split.
-      return new _Split<K, V>(sibling.keys[0], this, sibling);
+      tree._writeLeafNode(this);
+      tree._writeLeafNode(sibling);
+      return new _Split<K, N>(sibling.keys[0], id, sibling.id);
     }
     // The node was not full.
-    insertNotFull(key, value, index);
+    _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) {
+  _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V,
+      N> right) {
     // Find the key.
     int index = keys.indexOf(key);
     if (index == -1) {
       return new _Remove<K, V>(null);
     }
-    // Key key / value.
+    // Remove key / value.
     keys.removeAt(index);
     V value = values.removeAt(index);
+    tree._writeLeafNode(this);
     // Perform balancing.
     if (keys.length < minKeys) {
       // Try left sibling.
-      if (left is _LeafNode<K, V>) {
+      if (left is _LeafNode<K, V, N>) {
         // 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));
+          values.insertAll(0, left.values.getRange(newLeftLength,
+              leftLength));
           left.keys.length = newLeftLength;
           left.values.length = newLeftLength;
+          tree._writeLeafNode(this);
+          tree._writeLeafNode(left);
           return new _Remove<K, V>.borrowLeft(value, keys.first);
         }
         // Do merge.
         left.keys.addAll(keys);
         left.values.addAll(values);
+        tree._writeLeafNode(this);
+        tree._writeLeafNode(left);
         return new _Remove<K, V>.mergeLeft(value);
       }
       // Try right sibling.
-      if (right is _LeafNode<K, V>) {
+      if (right is _LeafNode<K, V, N>) {
         // 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);
+          tree._writeLeafNode(this);
+          tree._writeLeafNode(right);
           return new _Remove<K, V>.borrowRight(value, right.keys.first);
         }
         // Do merge.
         right.keys.insertAll(0, keys);
         right.values.insertAll(0, values);
+        tree._writeLeafNode(this);
+        tree._writeLeafNode(right);
         return new _Remove<K, V>.mergeRight(value);
       }
     }
     // No balancing required.
     return new _Remove<K, V>(value);
   }
 
   @override
   void writeOn(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');
   }
+
+  /**
+   * 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;
+  }
+
+  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);
+    }
+    tree._writeLeafNode(this);
+  }
 }
 
 
 /**
  * An internal or leaf node.
  */
-abstract class _Node<K, V> {
+abstract class _Node<K, V, N> {
   /**
    * The [Comparator] to compare keys.
    */
-  Comparator<K> comparator;
+  final Comparator<K> comparator;
+
+  /**
+   * The identifier of this node.
+   */
+  final N id;
 
   /**
    *  The list of keys.
    */
-  List<K> keys = new List<K>();
+  final List<K> keys = new List<K>();
 
-  _Node(this.comparator);
+  /**
+   * The [NodeManager] for this tree.
+   */
+  final NodeManager<K, V, N> manager;
+
+  /**
+   * The [BPlusTree] this node belongs to.
+   */
+  final BPlusTree<K, V, N> tree;
+
+  _Node(BPlusTree<K, V, N> tree, this.id)
+      : tree = tree,
+        comparator = tree._comparator,
+        manager = tree._manager;
 
   /**
    * 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);
+  _Split<K, N> 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);
+  _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V,
+      N> right);
 
   /**
    * Writes a textual presentation of the tree into [buffer].
    */
   void writeOn(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> {
+class _Split<K, N> {
   final K key;
-  final _Node<K, V> left;
-  final _Node<K, V> right;
+  final N left;
+  final N right;
   _Split(this.key, this.left, this.right);
 }