Overview
对MergingIterator的遍历会有序的遍历其child iterator中的每个元素。
因为iter_遍历的是数据库的每一条记录。它是以InternalKey(userkey, seq, type)为遍历粒度的，只要InternalKey中任意一个组成元素不同，MergingIterator就认为他们是不同的kv对。
而DBIter是以userkey为遍历粒度的，只要记录的userkey相同，那么DBIter就认为他们是一条记录（不同版本），sqe越大代表该记录越新。每次迭代将跳到下一个不同userkey的记录。
假设当前DBIter的sequence_为2，那么DBIter只会处理seq小于2的记录，这也是访问快照数据的原理。
图中每个框框表示对应记录的InternalKey(userkey, seq, type)，key1 < key2 < key3 < key4,seq越大代表记录越新，所以相同userkey的seq越大的顺序越靠前（小）。
Design 以下**
saved key
DBIter next的实现
假设iter_现在在key2:2:1的位置，DBIter也在这个位置，此时iter_的next会是key2:1:1。而DBIter的next将会是key4:2:1（因为key3:3:1seq不符，key3:2:0是一条删除记录，因此跳过key3:2:0和key3:1:1，key4:2:1seq不符）。
假设当前iter在key4:2:1上，direction为kForward。此时调用Prev()，此图显示了Prev操作执行的5个步骤。
S1 首先因为direction为kForward，先调整iter到key3:1:1上。此图也说明了调整的理由，key4:2:1前面还有key4:3:1。然后进入FindPrevUserEntry函数，执行S2到S4。
S2 跳到key3:2:0上时，这是一个删除标记，清空saved key（其中保存的是key3:1:1）。
S3 循环继续，跳到key2:1:1上，此时key2:1:1 > saved key，设置saved key为key2:1:1，并继续循环。
S4 循环继续，跳到key2:2:1上，此时key2:2:1 > saved key，设置saved key为key2:2:1，并继续循环。
S5 跳到Key1:1:1上，因为key1:1:1 < saved key，跳出循环。
最终状态iter_位置在key1:1:1上，而saved key保存的则是key2:2:1上，这也就是Prev应该定位到的值。也就是说在Prev操作下，iter_的位置并不是真正的key位置。这就是Get函数中，在direction为kReverse时，返回saved key/value的原因。
同理，在Next时，如果direction是kReverse，根据上面的Prev可以发现，此时iter刚好是saved key的前一个entry。执行iter->Next()就跳到了saved key的dentry范围的sequence最大的那个entry。在前面的例子中，在Prev后执行Next，那么iter首先跳转到key2:3:1上，然后再调用FindNextUserEntry循环，使iter定位在key2:2:1上。
prev的小结
prev就是要向前找到第一个符合条件的kv记录，该记录的userkey必须小于当前iter的userkey，并且该记录是最新的而且不能是删除类型的记录。如何判断出该记录是不是最新的呢，先将该记录保存在save（saved key/value）里，iter_继续向前遍历，如果遇到userkey和刚才save的记录userkey不相等的，则说明刚才save的就是最新的记录，此时iter_的位置并不是真正的key位置，saved key才是真正key的位置，因此需要用Direction来区分。
1） kForward，正向遍历（向后移动），代码保证此时DBIter的内部迭代器刚好定位在this->key(),this->value()这条记录上；此时iter_一定是在一条最新的记录上（seq最大的记录上（当然seq得小于sequence_））
2） kReverse，反向遍历（向前移动），代码保证此时DBIter的内部迭代器刚好定位在所有key=this->key()的entry之前。此时iter_一定是在一条最老的记录上。
其成员变量savedkey和saved value保存的是KReverse方向移动完成后的k/v对，每次seek系调用之后，其值都会跟随iter_而改变。
Detail Source Code Analysis
please look at my github: cld378632668
https://github.com/cld378632668/leveldb_chinese_comments
void DBIter::FindNextUserEntry(
void DBIter::FindPrevUserEntry()
Ref and Consult
http://blog.csdn.net/weixin_36145588/article/details/78690482
网友评论