mongodb的排序和嵌套数组排序用的是什么排序算法？

Question

我正在试验 MongoDB 的 sort 性能，以决定是否将用户的位置历史记录 {ts: DATE(), location: "loc"} (maxHistorySize=100) 存储在用户对象中或单独收集。

我的目标是获得更好的 TPS。预计写入比读取多得多。

我现在主要关心的是排序的性能（查询和内务管理以及插入（创建索引）时都需要排序）。

当存储在中时，写入查询将是这样的。我关心的是它能多快完成排序。由于每次插入时 $sort 运行，数组基本上已经排序了。我想知道 sort 的运行时间是 O(log(n)) 还是 O(nlog(n))

        update: {
          $setOnInsert: {userId: 'userId'},
          $push: {
            locations: {
              $each: [{location: 'location', ts: new Date()}],
              $slice: -100,
              $sort: {ts: 1}
            }
          },

单独存储时，我将不得不在ts上创建索引。由于 MongoDB 使用 B-tree 创建索引，我猜测开销仅为 O(log(n))。缺点是它使用额外的空间。

我不确定从哪里开始，任何建议都值得赞赏。谢谢

Answer 1

MongoDB 使用 std::sort (called from sortChildren called from PushNode::performPush.

我相信 std::sort 是 O(nlog(n))。

mongodb的排序和嵌套数组排序用的是什么排序算法？

What sorting alogrithm is used by mongodb's sort and nested array sort?

mongodb

performance

sorting

database-performance