1

我搜索在键值数据库中存储与键关联的列表的最佳方法（如berkleydb或leveldb）

例如：我有用户和用户之间的订单我想为每个用户存储订单 ID 列表，以便通过范围选择快速访问（用于分页）

如何存储这个结构？

我不想为每个用户以可序列化的格式存储它：

user_1_orders = serialize(1,2,3..)
user_2_orders = serialize(1,2,3..)

因为列表可能很长

我考虑为每个用户使用单独的数据库文件，并将商店订单 ID 作为其中的键，但这并不能解决范围选择问题。如果我想获取具有范围的用户 ID[5000:5050]怎么办？

我知道，但对诸如orredis之类的键值实现感兴趣。berkleydbleveldb

4

4 回答 4

2

让我们从一个列表开始。您可以使用单个哈希图：

  1. 在行中存储0用户订单的数量
  2. 对于每个新订单，存储一个新行，计数递增

所以 yoru hashmap 如下所示：

key | value
-------------
 0  |   5
 1  | tomato
 2  | celery
 3  | apple
 4  | pie
 5  | meat

密钥的稳定增量确保每个密钥都是唯一的。鉴于 db 是键排序的，并且 pack 函数将整数转换为一组正确排序的字节数组，您可以获取列表的切片。要获取 5000 到 5050 之间的订单，您可以使用 bsddbCursor.set_range或 leveldb createReadStream(js api)

现在让我们扩展到多个用户订单。如果你可以打开几个hashmap你可以使用上面使用的几个hashmap。也许您会遇到一些系统问题（打开 fds 的最大 nb 或每个目录的最大文件数）。因此，您可以使用单个并为多个用户共享相同的 hashmap。

我在下面解释的内容适用于 leveldb 和 bsddb，因为您pack使用字典顺序（字节顺序）正确键入。所以我会假设你有一个pack功能。在 bsddb 中，您必须自己构建一个pack函数。看看wiredtiger.packing或bytekey以获得灵感。

原理是使用用户的 id 来命名键。它也称为键组合。

假设您的数据库如下所示：

   key   |  value
-------------------
  1  | 0 |    2       <--- count column for user 1
  1  | 1 |  tomato
  1  | 2 |  orange 
    ...      ...
  32 | 0 |    1       <--- count column for user 32
  32 | 1 |  banna
    ...  |   ...

您使用以下（伪）代码创建此数据库：

db.put(pack(1, make_uid(1)), 'tomato')
db.put(pack(1, make_uid(1)), 'orange')
...
db.put(pack(32, make_uid(32)), 'bannana')

make_uid实现如下所示：

def make_uid(user_uid):
    # retrieve the current count
    counter_key = pack(user_uid, 0)
    value = db.get(counter_key)
    value += 1  # increment
    # save new count
    db.put(counter_key, value)
    return value

然后你必须进行正确的范围查找，它类似于单个复合键。使用 bsddb api cursor.set_range(key)，我们检索user5000和5050for user之间的所有项目42：

def user_orders_slice(user_id, start, end):
    key, value = cursor.set_range(pack(user_id, start))
    while True:
        user_id, order_id = unpack(key)
        if order_id > end:
            break
        else:
            # the value is probably packed somehow...
            yield value
            key, value = cursor.next()

不进行错误检查。除此之外user_orders_slice(42, 5000, 5050)，如果您从列表中删除项目，则不能保证切片会撕掉 51 个项目。查询说项目的正确方法50是实现 user_orders_query(user_id, start, limit)`。

我希望你能明白。

于 2015-08-21T22:20:27.403 回答
0

您可以使用 Redis 将列表存储在zset（排序集）中，如下所示：

// this line is called whenever a user place an order
$redis->zadd($user_1_orders, time(), $order_id);
// list orders of the user
$redis->zrange($user_1_orders, 0, -1);

Redis 足够快。但是关于 Redis 你应该知道的一件事是，它把所有的数据都存储在内存中，所以如果数据最终超出了物理内存，你必须自己对数据进行分片。

您也可以使用SSDB( https://github.com/ideawu/ssdb )，它是 的包装器leveldb，具有与 Redis 类似的 API，但将大部分数据存储在磁盘中，内存仅用于缓存。这意味着 SSDB 的容量是 Redis 的 100 倍——高达 TB。

于 2013-08-31T05:21:10.847 回答
0

在 BerkeleyDB 中，您可以按已排序或未排序的顺序存储每个键的多个值。这将是最自然的解决方案。LevelDB 没有这样的功能。不过，您应该查看LMDB( http://symas.com/mdb/ )，它还支持排序的多值键，并且比其他任何一个都更小、更快且更可靠。

于 2013-12-09T14:02:09.053 回答
0

您可以在支持扫描的键值存储（如 leveldb）中对此进行建模的一种方法是将订单 ID 添加到每个用户的键中。因此，每个订单的新键都是 userId_orderId。现在要获取特定用户的订单，您可以进行简单的前缀扫描 - scan(userId*)。现在这会使 userId 范围查询变慢，在这种情况下，您可以仅为 userIds 维护另一个表或使用另一个键约定： Id_userId 用于获取 [5000-5050] 之间的 userIds

最近我看到 hyperdex 在 leveldb 之上添加数据类型支持：例如：http ://hyperdex.org/doc/04.datatypes/#lists ，所以你也可以尝试一下。

于 2013-09-05T06:20:34.973 回答