Hacker News Reader

Comment by tidwall | Hacker News Reader

Integer keys are not uncommon. It's just that they are usually combined as key/value map entry, like the BTreeMap in Rust, such as BTreeMap[int, *myObj] or BTreeMap[string, string]. Another interesting use is ordered set like BTreeSet[int].

View on HN

That’s exactly my point, I would think BTree[struct { key int; val *whatever }] (index use case) or BTree[struct { key int; val inlineWhatever }] (heap use case) would be more common use cases than BTree[int] (int set use case), but probably less impressive delta on benchmarks.

It depends if they prefer array-of-structs versus struct-of-arrays layout. Isn't the latter usually faster?

I don’t understand your comment. What is “it”? Can you explain how BTree or each of the above use-cases relate to array-of-structs and struct-of-arrays concepts?

I think struct-of-arrays in this case would mean putting all the keys in one array and the values in a parallel array.

How do the two arrays you’re thinking of correspond to a BTree? If you’re thinking of two BTrees, how would that work? The BTree will sort the keys and values independently and they won’t line up - there’s nothing that maintains the associativity between the keys and values.

"Parallel" here means you don't change them independently. There is a constraint that they must always be in the same order, so key[i] corresponds to value[i]. Typically there is an API to do array operations like insert and delete that maintains this constraint.

So if you're sorting the keys and swap two of them, you make the same change to the values.

I know what struct-of-arrays is, but I am still wondering how struct-of-arrays relates to BTree. Are you imagining a BTree[key] and BTree[value]? How are associations maintained if the btrees sort independently?

Reply on news.ycombinator.com