physecfed wrote:
In a standard hashmap or dictionary, keys map to values in a 1:1 ratio; always 1:1. I'm looking at
this site's tutorials on the subject and it appears to show, like you said, N-1 keys for N links to downstream nodes.
What I'm not understanding is how does one get the Nth key for the other node?
What?
physecfed wrote:
I'm trying to think of this from an implementation perspective, where ideally one would be attempting to scale the tree with indirection using pointers. the notion of the key and the method used to logically link the tree (i.e. pointers) two different issues?
What? The tree "scales" by growing extra levels. That happens when nodes start filling up and have to be split because there's no room left for another key-value pair. So you get extra nodes and eventually extra levels (not talking about the details of re-balancing).
physecfed wrote:
Put it this way. If we have three nodes arranged so that two children are linked to the parent (or root), then the root, by the logic we've talked about, should have one key for two children. But that root (in a structural implementation) would have two pointers to the children.
Right. I see no reason for your "But", though. I'd say "And".
physecfed wrote:
So, even if you can verify that a key K exists in the tree T, how do you actually go about getting addresses from keys
Addresses of what?
physecfed wrote:
in order to scale the tree, when there are K+1 addresses for those K keys, and the memory addresses might not correspond in any way to the system of key ordering?
Within a node, keys and their respective values are logically tied/paired. You can have an array of k-v pairs in a node. Or you can have it split into two distinct arrays, an array of keys and an array of values, still directly corresponding to one another.
Obviously, if you want quick key search (which is the hole point of the data structure at hand), you keep the array of keys ordered/sorted. So, when you insert a new key between, let's say, key3 and key4 (because key3 < new key < key 4), you also insert its corresponding value between value3 and value4 (irrespective of how values relate to one another). The new key and its value both have the same index in separate arrays or in the same array, the index that used to belong to key4-value4 pair. key4-value4 moves one place.
The same ordering logic applies to links to children as those links are stuck between adjacent keys and there are two extra links on the sides.
I'm sorry, I'm having trouble understanding what it is that you don't understand.