3 ms·
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 BTre
by tidwall 4y ago
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].
- jitl 4y agoThat’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.
- skybrian 4y agoIt depends if they prefer array-of-structs versus struct-of-arrays layout. Isn't the latter usually faster?
- jitl 4y agoI 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?
- skybrian 4y agoI think struct-of-arrays in this case would mean putting all the keys in one array and the values in a parallel array.
- jitl 4y agoHow 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.
- skybrian 4y ago"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.
- jitl 4y agoI 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?