support iterator
roseduan opened this issue · 4 comments
+1
Hey team, i was thinking about keeping track of all memtables iterators and bbolt cursors when creating a new iterator and when iterating, making sure to always get the smaller element returned from all the iterators.
@roseduan @akiozihao lemme know your thoughts about this approach as i would like to take this
More thoughts:
im thinking about creating 2 sub-iterators: 1. DiskIndexIterator
, 2. MemoryIterator
both will implement the Iterator
interface. the reason for doing that is that the disk index is an interface itself and in order to be generic, one should implement iterator function for it.
** clients should not use those sub iterators since they will present partially correct sequence of data.
high level for DiskIndexIterator
/ MemoryIterator
:
the iterator will maintain a min heap (max heap if reversed) that will hold all current keys among all the internal iterators (all boltdb trees cursors/ all skiplist iterators). when calling for Key()
/ Value()
, it will be simply returned from heap with O(1) complexitiy.
after doing that, a dbIterator
struct will implement the Iterator
interface as well and will contain the both sub iterators.
the dbIterator
will implement all the needed logic to decide among the 2 iterators what is the next kv pair that needed to be returned.