search

cberner / redb

An embedded key-value database in pure Rust
https://www.redb.org
Apache License 2.0
3.07k stars 137 forks source link

Should sort order be a property of `TableDefinition` instead of the `K`? #790

Closed dpc closed 3 months ago

dpc commented 3 months ago

After playing a bit with it, I really do think that.

First, it would make trait Key unnecessary, which is a simplification. It is particularly beneficial for crates that will want to wrap redb in any way, e.g. for adding kv serialization, like I'm doing in redb-bincode, but also for any other purposes. Now they need to deal with just Value for both keys and values.

That trait does look weird the moment one look at it. It doesn't even refer to Self in any way.

IMO. Just logically the sorting order is not a property of the key, but the collection. Since the order is byte-comparison based it just doesn't fit on key, like e.g. std::ops::Ord does.

Having sort order on Key, makes it necessary to wrap the key type into some newtype, just to change order of the collection, which maybe was a good tradeoff in case of Ord, but for an ultimately byte-based comparison seems odd.

Having sort order on TableDefinition would make it possible to hide the whole thing and just default to what most people expect. AFAIK most key value stores doesn't even offer such a functionality, so most people will probably want just default lexicographical order. Why force them to deal with Key::cmp then?

What I propose:

pub struct TableDefinition<'a, K: Value + 'static, V: Value + 'static, S : SortOrder = LexicographicalOrder> { /* private fields */ }

Anyone who wants to change order in a particular collection, can just change S in TableDefinition and job done. Most users won't. And they will not need to impl Key for TheirTypes.

If the users do want to place with weird sort orders, they will then be able to re-use them, without wrapping keys in them somehow.

cberner commented 3 months ago

Thanks for the suggestion, but no I think the current design is better. You should think of Key::compare as effectively taking a &SelfType. The only reason it doesn't is in case implementations can be more efficient by avoiding a deserialization.