Hacker News Reader

Comment by mariorz | Hacker News Reader

In the case of a B-Tree the data structures are the keys/offsets (and possibly values) that are stored in the tree and not the tree itself.

I'm confused, you store values in the tree but in itself it is not a data structure?

Plus it is interesting that you view a B-Tree as an object - when I think about it, I categorise it as an "algorithm" operating on various data objects.

I see a B-tree as a data structure not an object per se, I still don't see how it would mean anything without its operations.

View on HN

Let me try and give an example. Let's assume we are modelling a non-leaf node which contains long keys and long offsets. We can do it in any of the following ways:

    |offset0|key1|offset1|key2|offset2|key3|offset3......|

    |key1|key2|key3...|offset0|offset1|offset2|offset3...|

    |offset0|offset1|offset2|offset3...|key1|key2|key3...|

    |count|key3|key1|key7...|offset0|offset1|offset2.....| <== Binary search-able keys

In all of these cases, the data structure is different but the basic B-Tree algorithm remains the same. You can implement the algorithm once (using templates (C++), macros (C), or a weakly typed language (Lisp/Scheme)) and re-use it with any and all data structures that come up later.

EDIT: Forgot offset0

how is Lisp/Scheme weakly typed? It is dynamically typed and strongly too(even though the strong/weak typing definition isn't exactly clear).

I'm sorry. You're right - that was a slip-up. I meant a non-static (dynamic) typed language.

Lisp/Scheme are untyped.

No, they're duck-typed. Types are attached to values, not variables, and for example trying to eval (+ 1 "hi") will throw a proper type exception.

You usually don't have to declare types but for example in Common Lisp you can optionally declare types for better performance in speed-critical parts of the code.

They're an implementation of the untyped lambda calculus. What you're thinking of are better named tags, not types.

I think you are both right. IMHO, a B-tree is a structure, but generally it's more of a meta structure. When you are doing something with a B-tree, you generally care about the contents of the tree, not the actual tree. The tree just happens to be the facility to efficiently manipulate the information that you really care about.

Also IMHO, code is data as well. So the definition of the b-tree operations (algorithms), the tree that they operate on, and the application data within the tree are all just data (some of them just happen to have a more direct effect on run time operations).

Reply on news.ycombinator.com