LMDB正向与反向遍历是否存在性能差异？

性能差异说明 #

B+树的正向与反向遍历几乎不存在性能差异。因为LMDB的B+树叶子节点采用双向链表结构，正向遍历是顺着链表的后继指针移动，反向遍历则是顺着前驱指针移动，二者的时间复杂度均为O(n)，底层磁盘IO次数、内存访问逻辑完全一致，不会出现明显的性能差距。

降序查询的可行性与方案 #

始终以降序方式查询完全可行，无需调整记录插入顺序，推荐两种方案：

• 直接使用反向遍历API：LMDB原生提供了反向遍历的接口，比如调用mdb_cursor_get时传入MDB_PREV或MDB_PREV_NEXT标志，就能直接从B+树的叶子节点链表尾部开始遍历，实现降序查询。这种方式无需修改存储逻辑，是最直接的实现方式。
• 自定义键排序规则：如果希望默认遍历即为降序，可以在创建LMDB环境时通过MDB_COMPARE选项指定自定义比较函数，让键以降序规则排序；也可以对键进行“反转编码”（比如字符串键反转存储、数值键取反后存储），此时正向遍历就等价于原键的降序遍历。不过这种方式需要在插入和查询时统一处理键的编码/解码，相比反向API会多一层逻辑开销。

关于插入顺序的说明 #

调整记录插入顺序对遍历性能没有任何帮助。B+树的节点排序完全由键的比较规则决定，插入顺序仅会影响树构建过程中的分裂次数，但最终叶子节点的链表顺序只和键的排序规则相关，和插入顺序无关。因此无论按升序还是降序插入，最终的遍历性能都保持一致。

内容的提问来源于stack exchange，提问作者Eloff