Backport B+ tree implementation from Dart to Java.

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';
 
 
 /**
@@ skipping 136 matching lines @@
       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));
+    _manager.writeIndex(node.id, new IndexNodeData<K, N>(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));
+    _manager.writeLeaf(node.id, new LeafNodeData<K, V>(node.keys, node.values));
   }
 }
 
 
 /**
  * A container with information about an index node.
  */
 class IndexNodeData<K, N> {
   final List<N> children;
   final List<K> keys;
@@ skipping 258 matching lines @@
         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, N>) {
         // Try to redistribute.
-        var rightLength = right.keys.length;
+        int 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);
@@ skipping 150 matching lines @@
         // 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, N>) {
         // Try to redistribute.
-        var rightLength = right.keys.length;
+        int 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);
         }
@@ skipping 140 matching lines @@
 
 /**
  * A container with information about split during insert.
  */
 class _Split<K, N> {
   final K key;
   final N left;
   final N right;
   _Split(this.key, this.left, this.right);
 }