向必须保证有序的数据里插入新数据，并获取新数据应在的位置，用什么数据结构比较好？

2019-09-23 20:52:26 +08:00
 1oNflow

数据都是数值类型，没有特定分布，新数据应在的位置的意思是插入这个数据后，从小到大排它是第几个。

想到可以用二叉搜索树，但是每次获取位置都要先插入，再从头遍历，效率可能有影响。

或者用有序链表，但是链表似乎不好存进数据库里。

想问下这种场景用什么数据结构比较好？

1092 次点击
所在节点    问与答
3 条回复
xupefei
2019-09-23 23:53:16 +08:00
改一个排序算法，在插入元素时返回最终确定的 index。
starsriver
2019-09-23 23:59:31 +08:00
既然是纯数值而且往数据库里面搁，那就直接主键有序，没必要用奇奇怪怪的算法。可能有重复的数据那就分统计表和数据表，用统计表的主键做为数据表的索引。
billlee
2019-09-24 00:32:25 +08:00
可以在二叉树的节点维护该节点的秩

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/603495

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX