search

ysono / pancake

7 stars 1 forks source link

Should memtable be a hashtable? #27

Closed ysono closed 3 years ago

ysono commented 3 years ago

With treemap: Get or insert: O(logn) Compact: It's O(n) to traverse right?

With hashmap: Get or insert: O(1) Compact: O(n logn). <-- whether we totally sort, or partially sort using priority queue.

ysono commented 3 years ago

If we want to allow range queries, it is natural to keep memtable as treemap.

If you all agree, we can close this issue.

btc commented 3 years ago

Indeed. The LSM::memtable seems best as an ordered map. lgn isn't too expensive for insertions especially since size is kept limited by periodic flush.

Compact: It's O(n) to traverse right?

Yeah!

Compact: O(n logn). <-- whether we totally sort, or partially sort using priority queue.

True!

btc commented 3 years ago

The SSTable::sparse_index might be a candidate for an alternate data structure though!