| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library index.b_plus_tree; | |
| 6 | |
| 7 import 'dart:collection'; | |
| 8 | |
| 9 | |
| 10 /** | |
| 11 * A simple B+ tree (http://en.wikipedia.org/wiki/B+_tree) implementation. | |
| 12 * | |
| 13 * [K] is the keys type. | |
| 14 * [V] is the values type. | |
| 15 * [N] is the type of node identifiers using by the [NodeManager]. | |
| 16 */ | |
| 17 class BPlusTree<K, V, N> { | |
| 18 /** | |
| 19 * The [Comparator] to compare keys. | |
| 20 */ | |
| 21 final Comparator<K> _comparator; | |
| 22 | |
| 23 /** | |
| 24 * The [NodeManager] to manage nodes. | |
| 25 */ | |
| 26 final NodeManager<K, V, N> _manager; | |
| 27 | |
| 28 /** | |
| 29 * The maximum number of keys in an index node. | |
| 30 */ | |
| 31 final int _maxIndexKeys; | |
| 32 | |
| 33 /** | |
| 34 * The maximum number of keys in a leaf node. | |
| 35 */ | |
| 36 final int _maxLeafKeys; | |
| 37 | |
| 38 /** | |
| 39 * The root node. | |
| 40 */ | |
| 41 _Node<K, V, N> _root; | |
| 42 | |
| 43 /** | |
| 44 * Creates a new [BPlusTree] instance. | |
| 45 */ | |
| 46 BPlusTree(this._comparator, NodeManager<K, V, N> manager) | |
| 47 : _manager = manager, | |
| 48 _maxIndexKeys = manager.maxIndexKeys, | |
| 49 _maxLeafKeys = manager.maxLeafKeys { | |
| 50 _root = _newLeafNode(); | |
| 51 _writeLeafNode(_root); | |
| 52 } | |
| 53 | |
| 54 /** | |
| 55 * Returns the value for [key] or `null` if [key] is not in the tree. | |
| 56 */ | |
| 57 V find(K key) { | |
| 58 return _root.find(key); | |
| 59 } | |
| 60 | |
| 61 /** | |
| 62 * Associates the [key] with the given [value]. | |
| 63 * | |
| 64 * If the key was already in the tree, its associated value is changed. | |
| 65 * Otherwise the key-value pair is added to the tree. | |
| 66 */ | |
| 67 void insert(K key, V value) { | |
| 68 _Split<K, N> result = _root.insert(key, value); | |
| 69 if (result != null) { | |
| 70 _IndexNode<K, V, N> newRoot = _newIndexNode(); | |
| 71 newRoot.keys.add(result.key); | |
| 72 newRoot.children.add(result.left); | |
| 73 newRoot.children.add(result.right); | |
| 74 _root = newRoot; | |
| 75 _writeIndexNode(_root); | |
| 76 } | |
| 77 } | |
| 78 | |
| 79 /** | |
| 80 * Removes the association for the given [key]. | |
| 81 * | |
| 82 * Returns the value associated with [key] in the tree or `null` if [key] is | |
| 83 * not in the tree. | |
| 84 */ | |
| 85 V remove(K key) { | |
| 86 _Remove<K, V> result = _root.remove(key, null, null, null); | |
| 87 if (_root is _IndexNode<K, V, N>) { | |
| 88 List<N> children = (_root as _IndexNode<K, V, N>).children; | |
| 89 if (children.length == 1) { | |
| 90 _manager.delete(_root.id); | |
| 91 _root = _readNode(children[0]); | |
| 92 } | |
| 93 } | |
| 94 return result.value; | |
| 95 } | |
| 96 | |
| 97 /** | |
| 98 * Writes a textual presentation of the tree into [buffer]. | |
| 99 */ | |
| 100 void writeOn(StringBuffer buffer) { | |
| 101 _root.writeOn(buffer, ''); | |
| 102 } | |
| 103 | |
| 104 /** | |
| 105 * Creates a new [_IndexNode] instance. | |
| 106 */ | |
| 107 _IndexNode<K, V, N> _newIndexNode() { | |
| 108 N id = _manager.createIndex(); | |
| 109 return new _IndexNode<K, V, N>(this, id, _maxIndexKeys); | |
| 110 } | |
| 111 | |
| 112 /** | |
| 113 * Creates a new [_LeafNode] instance. | |
| 114 */ | |
| 115 _LeafNode<K, V, N> _newLeafNode() { | |
| 116 N id = _manager.createLeaf(); | |
| 117 return new _LeafNode<K, V, N>(this, id, _maxLeafKeys); | |
| 118 } | |
| 119 | |
| 120 /** | |
| 121 * Reads the [_IndexNode] with [id] from the manager. | |
| 122 */ | |
| 123 _IndexNode<K, V, N> _readIndexNode(N id) { | |
| 124 IndexNodeData<K, N> data = _manager.readIndex(id); | |
| 125 _IndexNode<K, V, N> node = new _IndexNode<K, V, N>(this, id, _maxIndexKeys); | |
| 126 node.keys = data.keys; | |
| 127 node.children = data.children; | |
| 128 return node; | |
| 129 } | |
| 130 | |
| 131 /** | |
| 132 * Reads the [_LeafNode] with [id] from the manager. | |
| 133 */ | |
| 134 _LeafNode<K, V, N> _readLeafNode(N id) { | |
| 135 _LeafNode<K, V, N> node = new _LeafNode<K, V, N>(this, id, _maxLeafKeys); | |
| 136 LeafNodeData<K, V> data = _manager.readLeaf(id); | |
| 137 node.keys = data.keys; | |
| 138 node.values = data.values; | |
| 139 return node; | |
| 140 } | |
| 141 | |
| 142 /** | |
| 143 * Reads the [_IndexNode] or [_LeafNode] with [id] from the manager. | |
| 144 */ | |
| 145 _Node<K, V, N> _readNode(N id) { | |
| 146 if (_manager.isIndex(id)) { | |
| 147 return _readIndexNode(id); | |
| 148 } else { | |
| 149 return _readLeafNode(id); | |
| 150 } | |
| 151 } | |
| 152 | |
| 153 /** | |
| 154 * Writes [node] into the manager. | |
| 155 */ | |
| 156 void _writeIndexNode(_IndexNode<K, V, N> node) { | |
| 157 _manager.writeIndex(node.id, new IndexNodeData<K, N>(node.keys, node.childre
n)); | |
| 158 } | |
| 159 | |
| 160 /** | |
| 161 * Writes [node] into the manager. | |
| 162 */ | |
| 163 void _writeLeafNode(_LeafNode<K, V, N> node) { | |
| 164 _manager.writeLeaf(node.id, new LeafNodeData<K, V>(node.keys, node.values)); | |
| 165 } | |
| 166 } | |
| 167 | |
| 168 | |
| 169 /** | |
| 170 * A container with information about an index node. | |
| 171 */ | |
| 172 class IndexNodeData<K, N> { | |
| 173 final List<N> children; | |
| 174 final List<K> keys; | |
| 175 IndexNodeData(this.keys, this.children); | |
| 176 } | |
| 177 | |
| 178 | |
| 179 /** | |
| 180 * A container with information about a leaf node. | |
| 181 */ | |
| 182 class LeafNodeData<K, V> { | |
| 183 final List<K> keys; | |
| 184 final List<V> values; | |
| 185 LeafNodeData(this.keys, this.values); | |
| 186 } | |
| 187 | |
| 188 | |
| 189 /** | |
| 190 * An implementation of [NodeManager] that keeps node information in memory. | |
| 191 */ | |
| 192 class MemoryNodeManager<K, V> implements NodeManager<K, V, int> { | |
| 193 final int maxIndexKeys; | |
| 194 final int maxLeafKeys; | |
| 195 Map<int, IndexNodeData> _indexDataMap = new HashMap<int, IndexNodeData>(); | |
| 196 Map<int, LeafNodeData> _leafDataMap = new HashMap<int, LeafNodeData>(); | |
| 197 | |
| 198 int _nextPageIndexId = 0; | |
| 199 int _nextPageLeafId = 1; | |
| 200 | |
| 201 MemoryNodeManager(this.maxIndexKeys, this.maxLeafKeys); | |
| 202 | |
| 203 @override | |
| 204 int createIndex() { | |
| 205 int id = _nextPageIndexId; | |
| 206 _nextPageIndexId += 2; | |
| 207 return id; | |
| 208 } | |
| 209 | |
| 210 @override | |
| 211 int createLeaf() { | |
| 212 int id = _nextPageLeafId; | |
| 213 _nextPageLeafId += 2; | |
| 214 return id; | |
| 215 } | |
| 216 | |
| 217 @override | |
| 218 void delete(int id) { | |
| 219 if (isIndex(id)) { | |
| 220 _indexDataMap.remove(id); | |
| 221 } else { | |
| 222 _leafDataMap.remove(id); | |
| 223 } | |
| 224 } | |
| 225 | |
| 226 @override | |
| 227 bool isIndex(int id) { | |
| 228 return id.isEven; | |
| 229 } | |
| 230 | |
| 231 @override | |
| 232 IndexNodeData<K, int> readIndex(int id) { | |
| 233 return _indexDataMap[id]; | |
| 234 } | |
| 235 | |
| 236 @override | |
| 237 LeafNodeData<K, V> readLeaf(int id) { | |
| 238 return _leafDataMap[id]; | |
| 239 } | |
| 240 | |
| 241 @override | |
| 242 void writeIndex(int id, IndexNodeData<K, int> data) { | |
| 243 _indexDataMap[id] = data; | |
| 244 } | |
| 245 | |
| 246 @override | |
| 247 void writeLeaf(int id, LeafNodeData<K, V> data) { | |
| 248 _leafDataMap[id] = data; | |
| 249 } | |
| 250 } | |
| 251 | |
| 252 | |
| 253 /** | |
| 254 * A manager that manages nodes. | |
| 255 */ | |
| 256 abstract class NodeManager<K, V, N> { | |
| 257 /** | |
| 258 * The maximum number of keys in an index node. | |
| 259 */ | |
| 260 int get maxIndexKeys; | |
| 261 | |
| 262 /** | |
| 263 * The maximum number of keys in a leaf node. | |
| 264 */ | |
| 265 int get maxLeafKeys; | |
| 266 | |
| 267 /** | |
| 268 * Generates an identifier for a new index node. | |
| 269 */ | |
| 270 N createIndex(); | |
| 271 | |
| 272 /** | |
| 273 * Generates an identifier for a new leaf node. | |
| 274 */ | |
| 275 N createLeaf(); | |
| 276 | |
| 277 /** | |
| 278 * Deletes the node with the given identifier. | |
| 279 */ | |
| 280 void delete(N id); | |
| 281 | |
| 282 /** | |
| 283 * Checks if the node with the given identifier is an index or a leaf node. | |
| 284 */ | |
| 285 bool isIndex(N id); | |
| 286 | |
| 287 /** | |
| 288 * Reads information about the index node with the given identifier. | |
| 289 */ | |
| 290 IndexNodeData<K, N> readIndex(N id); | |
| 291 | |
| 292 /** | |
| 293 * Reads information about the leaf node with the given identifier. | |
| 294 */ | |
| 295 LeafNodeData<K, V> readLeaf(N id); | |
| 296 | |
| 297 /** | |
| 298 * Writes information about the index node with the given identifier. | |
| 299 */ | |
| 300 void writeIndex(N id, IndexNodeData<K, N> data); | |
| 301 | |
| 302 /** | |
| 303 * Writes information about the leaf node with the given identifier. | |
| 304 */ | |
| 305 void writeLeaf(N id, LeafNodeData<K, V> data); | |
| 306 } | |
| 307 | |
| 308 | |
| 309 /** | |
| 310 * An index node with keys and children references. | |
| 311 */ | |
| 312 class _IndexNode<K, V, N> extends _Node<K, V, N> { | |
| 313 List<N> children = new List<N>(); | |
| 314 final int maxKeys; | |
| 315 final int minKeys; | |
| 316 | |
| 317 _IndexNode(BPlusTree<K, V, N> tree, N id, int maxKeys) | |
| 318 : super(tree, id), | |
| 319 maxKeys = maxKeys, | |
| 320 minKeys = maxKeys ~/ 2; | |
| 321 | |
| 322 @override | |
| 323 V find(K key) { | |
| 324 int index = _findChildIndex(key); | |
| 325 _Node<K, V, N> child = tree._readNode(children[index]); | |
| 326 return child.find(key); | |
| 327 } | |
| 328 | |
| 329 _Split<K, N> insert(K key, V value) { | |
| 330 // Early split. | |
| 331 if (keys.length == maxKeys) { | |
| 332 int middle = (maxKeys + 1) ~/ 2; | |
| 333 K splitKey = keys[middle]; | |
| 334 // Overflow into a new sibling. | |
| 335 _IndexNode<K, V, N> sibling = tree._newIndexNode(); | |
| 336 sibling.keys.addAll(keys.getRange(middle + 1, keys.length)); | |
| 337 sibling.children.addAll(children.getRange(middle + 1, children.length)); | |
| 338 keys.length = middle; | |
| 339 children.length = middle + 1; | |
| 340 // Insert into this node or sibling. | |
| 341 if (comparator(key, splitKey) < 0) { | |
| 342 _insertNotFull(key, value); | |
| 343 } else { | |
| 344 sibling._insertNotFull(key, value); | |
| 345 } | |
| 346 // Prepare split. | |
| 347 tree._writeIndexNode(this); | |
| 348 tree._writeIndexNode(sibling); | |
| 349 return new _Split<K, N>(splitKey, id, sibling.id); | |
| 350 } | |
| 351 // No split. | |
| 352 _insertNotFull(key, value); | |
| 353 return null; | |
| 354 } | |
| 355 | |
| 356 @override | |
| 357 _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V, | |
| 358 N> right) { | |
| 359 int index = _findChildIndex(key); | |
| 360 K thisAnchor = index == 0 ? keys[0] : keys[index - 1]; | |
| 361 // Prepare children. | |
| 362 _Node<K, V, N> child = tree._readNode(children[index]); | |
| 363 _Node<K, V, N> leftChild; | |
| 364 _Node<K, V, N> rightChild; | |
| 365 if (index != 0) { | |
| 366 leftChild = tree._readNode(children[index - 1]); | |
| 367 } else { | |
| 368 leftChild = null; | |
| 369 } | |
| 370 if (index < children.length - 1) { | |
| 371 rightChild = tree._readNode(children[index + 1]); | |
| 372 } else { | |
| 373 rightChild = null; | |
| 374 } | |
| 375 // Ask child to remove. | |
| 376 _Remove<K, V> result = child.remove(key, leftChild, thisAnchor, rightChild); | |
| 377 V value = result.value; | |
| 378 if (value == null) { | |
| 379 return new _Remove<K, V>(value); | |
| 380 } | |
| 381 // Do keys / children updates | |
| 382 bool hasUpdates = false; | |
| 383 { | |
| 384 // Update anchor if borrowed. | |
| 385 if (result.leftAnchor != null) { | |
| 386 keys[index - 1] = result.leftAnchor; | |
| 387 hasUpdates = true; | |
| 388 } | |
| 389 if (result.rightAnchor != null) { | |
| 390 keys[index] = result.rightAnchor; | |
| 391 hasUpdates = true; | |
| 392 } | |
| 393 // Update keys / children if merged. | |
| 394 if (result.mergedLeft) { | |
| 395 keys.removeAt(index - 1); | |
| 396 N child = children.removeAt(index); | |
| 397 manager.delete(child); | |
| 398 hasUpdates = true; | |
| 399 } | |
| 400 if (result.mergedRight) { | |
| 401 keys.removeAt(index); | |
| 402 N child = children.removeAt(index); | |
| 403 manager.delete(child); | |
| 404 hasUpdates = true; | |
| 405 } | |
| 406 } | |
| 407 // Write if updated. | |
| 408 if (!hasUpdates) { | |
| 409 return new _Remove<K, V>(value); | |
| 410 } | |
| 411 tree._writeIndexNode(this); | |
| 412 // Perform balancing. | |
| 413 if (keys.length < minKeys) { | |
| 414 // Try left sibling. | |
| 415 if (left is _IndexNode<K, V, N>) { | |
| 416 // Try to redistribute. | |
| 417 int leftLength = left.keys.length; | |
| 418 if (leftLength > minKeys) { | |
| 419 int halfExcess = (leftLength - minKeys + 1) ~/ 2; | |
| 420 int newLeftLength = leftLength - halfExcess; | |
| 421 keys.insert(0, anchor); | |
| 422 keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength)); | |
| 423 children.insertAll(0, left.children.getRange(newLeftLength, leftLength | |
| 424 + 1)); | |
| 425 K newAnchor = left.keys[newLeftLength - 1]; | |
| 426 left.keys.length = newLeftLength - 1; | |
| 427 left.children.length = newLeftLength; | |
| 428 tree._writeIndexNode(this); | |
| 429 tree._writeIndexNode(left); | |
| 430 return new _Remove<K, V>.borrowLeft(value, newAnchor); | |
| 431 } | |
| 432 // Do merge. | |
| 433 left.keys.add(anchor); | |
| 434 left.keys.addAll(keys); | |
| 435 left.children.addAll(children); | |
| 436 tree._writeIndexNode(this); | |
| 437 tree._writeIndexNode(left); | |
| 438 return new _Remove<K, V>.mergeLeft(value); | |
| 439 } | |
| 440 // Try right sibling. | |
| 441 if (right is _IndexNode<K, V, N>) { | |
| 442 // Try to redistribute. | |
| 443 int rightLength = right.keys.length; | |
| 444 if (rightLength > minKeys) { | |
| 445 int halfExcess = (rightLength - minKeys + 1) ~/ 2; | |
| 446 keys.add(anchor); | |
| 447 keys.addAll(right.keys.getRange(0, halfExcess - 1)); | |
| 448 children.addAll(right.children.getRange(0, halfExcess)); | |
| 449 K newAnchor = right.keys[halfExcess - 1]; | |
| 450 right.keys.removeRange(0, halfExcess); | |
| 451 right.children.removeRange(0, halfExcess); | |
| 452 tree._writeIndexNode(this); | |
| 453 tree._writeIndexNode(right); | |
| 454 return new _Remove<K, V>.borrowRight(value, newAnchor); | |
| 455 } | |
| 456 // Do merge. | |
| 457 right.keys.insert(0, anchor); | |
| 458 right.keys.insertAll(0, keys); | |
| 459 right.children.insertAll(0, children); | |
| 460 tree._writeIndexNode(this); | |
| 461 tree._writeIndexNode(right); | |
| 462 return new _Remove<K, V>.mergeRight(value); | |
| 463 } | |
| 464 } | |
| 465 // No balancing required. | |
| 466 return new _Remove<K, V>(value); | |
| 467 } | |
| 468 | |
| 469 @override | |
| 470 void writeOn(StringBuffer buffer, String indent) { | |
| 471 buffer.write(indent); | |
| 472 buffer.write('INode {\n'); | |
| 473 for (int i = 0; i < keys.length; i++) { | |
| 474 _Node<K, V, N> child = tree._readNode(children[i]); | |
| 475 child.writeOn(buffer, indent + ' '); | |
| 476 buffer.write(indent); | |
| 477 buffer.write(' '); | |
| 478 buffer.write(keys[i]); | |
| 479 buffer.write('\n'); | |
| 480 } | |
| 481 _Node<K, V, N> child = tree._readNode(children[keys.length]); | |
| 482 child.writeOn(buffer, indent + ' '); | |
| 483 buffer.write(indent); | |
| 484 buffer.write('}\n'); | |
| 485 } | |
| 486 | |
| 487 /** | |
| 488 * Returns the index of the child into which [key] should be inserted. | |
| 489 */ | |
| 490 int _findChildIndex(K key) { | |
| 491 int lo = 0; | |
| 492 int hi = keys.length - 1; | |
| 493 while (lo <= hi) { | |
| 494 int mid = lo + (hi - lo) ~/ 2; | |
| 495 int compare = comparator(key, keys[mid]); | |
| 496 if (compare < 0) { | |
| 497 hi = mid - 1; | |
| 498 } else if (compare > 0) { | |
| 499 lo = mid + 1; | |
| 500 } else { | |
| 501 return mid + 1; | |
| 502 } | |
| 503 } | |
| 504 return lo; | |
| 505 } | |
| 506 | |
| 507 void _insertNotFull(K key, V value) { | |
| 508 int index = _findChildIndex(key); | |
| 509 _Node<K, V, N> child = tree._readNode(children[index]); | |
| 510 _Split<K, N> result = child.insert(key, value); | |
| 511 if (result != null) { | |
| 512 keys.insert(index, result.key); | |
| 513 children[index] = result.left; | |
| 514 children.insert(index + 1, result.right); | |
| 515 tree._writeIndexNode(this); | |
| 516 } | |
| 517 } | |
| 518 } | |
| 519 | |
| 520 | |
| 521 /** | |
| 522 * A leaf node with keys and values. | |
| 523 */ | |
| 524 class _LeafNode<K, V, N> extends _Node<K, V, N> { | |
| 525 final int maxKeys; | |
| 526 final int minKeys; | |
| 527 List<V> values = new List<V>(); | |
| 528 | |
| 529 _LeafNode(BPlusTree<K, V, N> tree, N id, int maxKeys) | |
| 530 : super(tree, id), | |
| 531 maxKeys = maxKeys, | |
| 532 minKeys = maxKeys ~/ 2; | |
| 533 | |
| 534 @override | |
| 535 V find(K key) { | |
| 536 int index = _findKeyIndex(key); | |
| 537 if (index < 0) { | |
| 538 return null; | |
| 539 } | |
| 540 if (index >= keys.length) { | |
| 541 return null; | |
| 542 } | |
| 543 if (keys[index] != key) { | |
| 544 return null; | |
| 545 } | |
| 546 return values[index]; | |
| 547 } | |
| 548 | |
| 549 _Split<K, N> insert(K key, V value) { | |
| 550 int index = _findKeyIndex(key); | |
| 551 // The node is full. | |
| 552 if (keys.length == maxKeys) { | |
| 553 int middle = (maxKeys + 1) ~/ 2; | |
| 554 _LeafNode<K, V, N> sibling = tree._newLeafNode(); | |
| 555 sibling.keys.addAll(keys.getRange(middle, keys.length)); | |
| 556 sibling.values.addAll(values.getRange(middle, values.length)); | |
| 557 keys.length = middle; | |
| 558 values.length = middle; | |
| 559 // Insert into the left / right sibling. | |
| 560 if (index < middle) { | |
| 561 _insertNotFull(key, value, index); | |
| 562 } else { | |
| 563 sibling._insertNotFull(key, value, index - middle); | |
| 564 } | |
| 565 // Notify the parent about the split. | |
| 566 tree._writeLeafNode(this); | |
| 567 tree._writeLeafNode(sibling); | |
| 568 return new _Split<K, N>(sibling.keys[0], id, sibling.id); | |
| 569 } | |
| 570 // The node was not full. | |
| 571 _insertNotFull(key, value, index); | |
| 572 return null; | |
| 573 } | |
| 574 | |
| 575 @override | |
| 576 _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V, | |
| 577 N> right) { | |
| 578 // Find the key. | |
| 579 int index = keys.indexOf(key); | |
| 580 if (index == -1) { | |
| 581 return new _Remove<K, V>(null); | |
| 582 } | |
| 583 // Remove key / value. | |
| 584 keys.removeAt(index); | |
| 585 V value = values.removeAt(index); | |
| 586 tree._writeLeafNode(this); | |
| 587 // Perform balancing. | |
| 588 if (keys.length < minKeys) { | |
| 589 // Try left sibling. | |
| 590 if (left is _LeafNode<K, V, N>) { | |
| 591 // Try to redistribute. | |
| 592 int leftLength = left.keys.length; | |
| 593 if (leftLength > minKeys) { | |
| 594 int halfExcess = (leftLength - minKeys + 1) ~/ 2; | |
| 595 int newLeftLength = leftLength - halfExcess; | |
| 596 keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength)); | |
| 597 values.insertAll(0, left.values.getRange(newLeftLength, leftLength)); | |
| 598 left.keys.length = newLeftLength; | |
| 599 left.values.length = newLeftLength; | |
| 600 tree._writeLeafNode(this); | |
| 601 tree._writeLeafNode(left); | |
| 602 return new _Remove<K, V>.borrowLeft(value, keys.first); | |
| 603 } | |
| 604 // Do merge. | |
| 605 left.keys.addAll(keys); | |
| 606 left.values.addAll(values); | |
| 607 tree._writeLeafNode(this); | |
| 608 tree._writeLeafNode(left); | |
| 609 return new _Remove<K, V>.mergeLeft(value); | |
| 610 } | |
| 611 // Try right sibling. | |
| 612 if (right is _LeafNode<K, V, N>) { | |
| 613 // Try to redistribute. | |
| 614 int rightLength = right.keys.length; | |
| 615 if (rightLength > minKeys) { | |
| 616 int halfExcess = (rightLength - minKeys + 1) ~/ 2; | |
| 617 keys.addAll(right.keys.getRange(0, halfExcess)); | |
| 618 values.addAll(right.values.getRange(0, halfExcess)); | |
| 619 right.keys.removeRange(0, halfExcess); | |
| 620 right.values.removeRange(0, halfExcess); | |
| 621 tree._writeLeafNode(this); | |
| 622 tree._writeLeafNode(right); | |
| 623 return new _Remove<K, V>.borrowRight(value, right.keys.first); | |
| 624 } | |
| 625 // Do merge. | |
| 626 right.keys.insertAll(0, keys); | |
| 627 right.values.insertAll(0, values); | |
| 628 tree._writeLeafNode(this); | |
| 629 tree._writeLeafNode(right); | |
| 630 return new _Remove<K, V>.mergeRight(value); | |
| 631 } | |
| 632 } | |
| 633 // No balancing required. | |
| 634 return new _Remove<K, V>(value); | |
| 635 } | |
| 636 | |
| 637 @override | |
| 638 void writeOn(StringBuffer buffer, String indent) { | |
| 639 buffer.write(indent); | |
| 640 buffer.write('LNode {'); | |
| 641 for (int i = 0; i < keys.length; i++) { | |
| 642 if (i != 0) { | |
| 643 buffer.write(', '); | |
| 644 } | |
| 645 buffer.write(keys[i]); | |
| 646 buffer.write(': '); | |
| 647 buffer.write(values[i]); | |
| 648 } | |
| 649 buffer.write('}\n'); | |
| 650 } | |
| 651 | |
| 652 /** | |
| 653 * Returns the index where [key] should be inserted. | |
| 654 */ | |
| 655 int _findKeyIndex(K key) { | |
| 656 int lo = 0; | |
| 657 int hi = keys.length - 1; | |
| 658 while (lo <= hi) { | |
| 659 int mid = lo + (hi - lo) ~/ 2; | |
| 660 int compare = comparator(key, keys[mid]); | |
| 661 if (compare < 0) { | |
| 662 hi = mid - 1; | |
| 663 } else if (compare > 0) { | |
| 664 lo = mid + 1; | |
| 665 } else { | |
| 666 return mid; | |
| 667 } | |
| 668 } | |
| 669 return lo; | |
| 670 } | |
| 671 | |
| 672 void _insertNotFull(K key, V value, int index) { | |
| 673 if (index < keys.length && comparator(keys[index], key) == 0) { | |
| 674 values[index] = value; | |
| 675 } else { | |
| 676 keys.insert(index, key); | |
| 677 values.insert(index, value); | |
| 678 } | |
| 679 tree._writeLeafNode(this); | |
| 680 } | |
| 681 } | |
| 682 | |
| 683 | |
| 684 /** | |
| 685 * An internal or leaf node. | |
| 686 */ | |
| 687 abstract class _Node<K, V, N> { | |
| 688 /** | |
| 689 * The [Comparator] to compare keys. | |
| 690 */ | |
| 691 final Comparator<K> comparator; | |
| 692 | |
| 693 /** | |
| 694 * The identifier of this node. | |
| 695 */ | |
| 696 final N id; | |
| 697 | |
| 698 /** | |
| 699 * The list of keys. | |
| 700 */ | |
| 701 List<K> keys = new List<K>(); | |
| 702 | |
| 703 /** | |
| 704 * The [NodeManager] for this tree. | |
| 705 */ | |
| 706 final NodeManager<K, V, N> manager; | |
| 707 | |
| 708 /** | |
| 709 * The [BPlusTree] this node belongs to. | |
| 710 */ | |
| 711 final BPlusTree<K, V, N> tree; | |
| 712 | |
| 713 _Node(BPlusTree<K, V, N> tree, this.id) | |
| 714 : tree = tree, | |
| 715 comparator = tree._comparator, | |
| 716 manager = tree._manager; | |
| 717 | |
| 718 /** | |
| 719 * Looks for [key]. | |
| 720 * | |
| 721 * Returns the associated value if found. | |
| 722 * Returns `null` if not found. | |
| 723 */ | |
| 724 V find(K key); | |
| 725 | |
| 726 /** | |
| 727 * Inserts the [key] / [value] pair into this [_Node]. | |
| 728 * | |
| 729 * Returns a [_Split] object if split happens, or `null` otherwise. | |
| 730 */ | |
| 731 _Split<K, N> insert(K key, V value); | |
| 732 | |
| 733 /** | |
| 734 * Removes the association for the given [key]. | |
| 735 * | |
| 736 * Returns the [_Remove] information about an operation performed. | |
| 737 * It may be restructuring or merging, with [left] or [left] siblings. | |
| 738 */ | |
| 739 _Remove<K, V> remove(K key, _Node<K, V, N> left, K anchor, _Node<K, V, | |
| 740 N> right); | |
| 741 | |
| 742 /** | |
| 743 * Writes a textual presentation of the tree into [buffer]. | |
| 744 */ | |
| 745 void writeOn(StringBuffer buffer, String indent); | |
| 746 } | |
| 747 | |
| 748 | |
| 749 /** | |
| 750 * A container with information about redistribute / merge. | |
| 751 */ | |
| 752 class _Remove<K, V> { | |
| 753 K leftAnchor; | |
| 754 bool mergedLeft = false; | |
| 755 bool mergedRight = false; | |
| 756 K rightAnchor; | |
| 757 final V value; | |
| 758 _Remove(this.value); | |
| 759 _Remove.borrowLeft(this.value, this.leftAnchor); | |
| 760 _Remove.borrowRight(this.value, this.rightAnchor); | |
| 761 _Remove.mergeLeft(this.value) : mergedLeft = true; | |
| 762 _Remove.mergeRight(this.value) : mergedRight = true; | |
| 763 } | |
| 764 | |
| 765 | |
| 766 /** | |
| 767 * A container with information about split during insert. | |
| 768 */ | |
| 769 class _Split<K, N> { | |
| 770 final K key; | |
| 771 final N left; | |
| 772 final N right; | |
| 773 _Split(this.key, this.left, this.right); | |
| 774 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 365193004:
Move Index and IndexStore implementations into Engine. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart