c - 快速搜索双向链表

Question

我目前有一个简单的数据库程序，它从文本文件中读取键并将它们存储在双向链表中(如果需要，稍后读取值)。目前，我在列表上进行顺序搜索，但这显然很慢。我希望有另一种方法。我正在阅读有关二叉树(特别是红黑树)的信息，但我对它们知之甚少，并希望我能从 stackoverflow hivemind 中得到一些东西 :) 我想我的问题是，最快的方法是什么在双向链表中进行搜索？

编辑:忘了说列表是排序的。不知道这是否改变了什么。另外，我只读keys的原因是max value length是1024*32 bytes，感觉太大了。请注意，这是针对作业的，因此“典型使用场景”不适用。教授们可能会对这件事进行压力测试，我不想分配那么大的 block 。

Answer 1

有一个叫做“skip list”的东西你可以使用。

它是一组有序列表。每个列表都会跳过更多的列表项。这使您可以进行某种形式的二进制搜索。但是，维护列表更加困难。