javascript - nodejs百万条数据的排序

Question

百万条数据的排序。环境是nodejs，有个object，里面的东西很简单，就是 key=>value 格式而已

let keys = Object.keys(data);

光这一步我执行就费了一秒钟的时间了。

循环一次，耗费了1.5秒。

还有得搞吗？
我不知道人家那种一秒钟不到，把数据排列并且搜索的怎么弄的，太神奇了。

-----------------补充----------------------

下面的回答关注点都在需求上面了。详细说一下。

1、首先是nodejs环境，不是真正的前端。这个我上面没有说，但不影响解决问题。

2、下面的回答都角度都是什么先展示几页啥的，我没说展示百万条数据，我只是排序，搜索。
比如，我搜索 key=abc ， 第 100条，列出 50个数据，按照key排序列出， 你难道不是从这100万条数据去搜索、排序吗？难道你要从前50条里面去操作吗？

我操作100万条，我可没说展示100万条。。。这个得看清楚。

3、具体情况是这样的。底层数据存储使用leveldb，leveldb都是存储在硬盘里面，单个key搜索还是挺快的。但是你要搞个排序、分页，他得把100万条数据从硬盘里面一个一个读取，然后你再进行操作。

按照他那样，读取完一次，估计4分钟。从硬盘读取，速度肯定很慢了，不过他也有好处，内存占用小。不然你10G的东西，都一次性拿出来再操作，可想而知……

所以，解决的办法，自己生成索引。把索引放到一个文件里面，查询的时候一次性加载进来，放到内存，这样就比你把100万篇文章从硬盘一个一个找出来再排序高效很多。
比如 id=>dateline 这样的形式，保存id和时间，如果你想按照时间进行排序，那么就可以对索引进行排序，比如取出50个id出来，然后再去硬盘读取这50个就行了

因为索引文件很小，只是保存了一些简单得不能再简单的数据，所以百万条数据，加起来不过几十MB，这样内存占用也是很低的。

4、像这种情况，索引使用Redis存储应该是一个不错的解决方案，但环境不允许。环境允许的话，我使用mysql之类的存储就好了。

Answer 1

let keys = Object.keys(data);

这一句相当于遍历所有的元素，用时间复杂度表示为O(n*x)，x为查找一个元素所需要的平均时间复杂度。js的{}类型应该采用了一种平衡树，平衡树查找一次最好的复杂度也是O(logn)，也就是说上面这一句的时间复杂度最好也得是O(nlogn)，因为{}类型还要有其他的一些方法，所有平衡树的性能并不会是最好的，实际运行的时间必然会高于理论估计的O(nlogn)。

而题主你目前的实际情况是：data是一个有100w数据量级别集合，你需要对键值进行排序，js的这一句执行一次却需要1.5s 。

解决方法：

1. js就是慢，换一种语言去处理你的这个索引集合，比如C++之类的。缺点就是js如果需要不同的键值顺序，每次都得重新计算；如果存储的数据进行了修改或者删除，这个索引也得重新计算。

2. 数据库也是可以建立索引来提高搜索速度的；

3. 实际上，{}存储的数据本来就是有序的，这个可以查一下排序二叉树，对于输出100w的前50个数据这种问题，只需要：

   var num = 0;
   for(var x in data){
   if(num < 50) num++;
   else break;
   // your code used to deal data[x]
   }
      

看了一下题主的其他评论，得知题主的目标：根据某一键值的将数据排序，取第x个，数据量高达100w。

那无论如何都得读100w条数据，我感觉没法再大幅度提升速度了，算法复杂度O(nlogn)的方法都执行1.5s, 而这个已经是理论的最低限度了。

Answer 2

因为人家不是一次性就把所有的数据都吐出来，一般来说都是先吐1-2页的数据显示，剩下的大概都是懒加载或者搜索时再加载之类的

Answer 3

我觉得也是分页，先展示前几页，根据需要再去请求后面的数据

Answer 4

哪个网站是前端在进行百万条数据排序的，能不能举个例子？

---------- 补充 -----------

看了题主的补充，我个人感觉这和js没什么关系，完全是数据库层面的东西。

Answer 5

这个其实不算是前端的问题了。这个就是搜索优化的问题。node也应该有自己搭配的数据库吧。找一个做好的数据库。你现在这样就等于自己写一个数据库。

Answer 6

变量占用内存过大
确认别人1秒内解决的, 机器配置cpu和内存和你的相比如何

排除以上
你的百万数据data 怎么不是数组, 数组可以分割处理, object 一次遍历内占满内存了
而数组的话 let keys = 这步可以去掉了(省下keys占用的内存)

data.sort(function(a, b){
    // 按记录某字段排序
    return a.key - b.key;
});
return data;