A simple B+Tree implementation.

A simple B+Tree implementation.

R=brianwilkerson@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=37113

[kasperl, 2014-06-07 11:34:15]

Have you considered letting this implement the Map interface? Also, this looks
like it might be a good fit for the dart:collection library and that would allow
others to benefit from your data structure too.

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

LGTM

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/index/btree.dart (right):

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:9: * A simple B+Tree
implementation.
"B+Tree" --> "B-Tree"

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:61: if (invocation.memberName ==
#debugPrint) {
Why not just make debugPrint a public method? Doesn't this have the same effect
(other than hiding it from code completion)?

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:88: void _debugPrint(StringBuffer
buffer) {
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".

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:97: class _INode<K, V> extends
_Node<K, V> {
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.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:125: _Split insert(K key, V value)
{
"_Split" --> "_Split<K, V>"

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:406: abstract class _Node<K, V> {
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.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/test...
File pkg/analysis_server/test/index/btree_test.dart (right):

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/test...
pkg/analysis_server/test/index/btree_test.dart:25: //  print(dump);
Remove?

[scheglov, 2014-06-07 21:26:23]

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/index/btree.dart (right):

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:9: * A simple B+Tree
implementation.
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> "B+Tree" --> "B-Tree"

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.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:61: if (invocation.memberName ==
#debugPrint) {
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> Why not just make debugPrint a public method? Doesn't this have the same
effect
> (other than hiding it from code completion)?

OK, I think we can make it public again.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:88: void _debugPrint(StringBuffer
buffer) {
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> 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.

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


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

Done.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:97: class _INode<K, V> extends
_Node<K, V> {
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> 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.

Done.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:125: _Split insert(K key, V value)
{
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> "_Split" --> "_Split<K, V>"

Done.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:406: abstract class _Node<K, V> {
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> 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.

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.

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/test...
File pkg/analysis_server/test/index/btree_test.dart (right):

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/test...
pkg/analysis_server/test/index/btree_test.dart:25: //  print(dump);
On 2014/06/07 16:34:02, Brian Wilkerson wrote:
> Remove?

Done.

[scheglov, 2014-06-07 21:36:35]

Committed patchset #4 manually as r37113 (presubmit successful).

[scheglov, 2014-06-07 21:38:50]

On 2014/06/07 11:34:15, kasperl wrote:
> Have you considered letting this implement the Map interface? Also, this looks
> like it might be a good fit for the dart:collection library and that would
allow
> others to benefit from your data structure too.

Not yet, but I will check how much should be implemented additionally for
implement the Map interface.

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

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/index/btree.dart (right):

https://codereview.chromium.org/314413004/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/btree.dart:9: * A simple B+Tree
implementation.
> It is actually not a mistake.
> It is a B+Tree flavor of B-Tree.

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.