类似数组的数据结构在插入和插入方面高效找时间

Question

我需要一个用 Ruby 语言实现的数据结构来容纳大量不同的 url（例如 10**10 段），因此性能是我关心的问题。 我使用 Array 并保持其元素有序，因此我可以执行二分搜索 来查找是否已存在或在何处快速插入 url。 我是这样写的：

class UrlStore
    def initialize(*args)
        @urls = []
        args.each { |e| add(e) unless e.class != String }
    end

    def add(url)
        p = find(url)
        @urls.insert(p, url) unless p.class == String
    end


    def find(url)
        l, m, h = 0, 0, @urls.size - 1

        while l <= h do
            m = l + (h - l) / 2
            b = url <=> @urls[m]
            if b == 0
                return m.to_s
            elsif b == 1
                l = m + 1
            else
                h = m - 1
            end
        end

        return l
    end
end

如果找到的话，find 方法将返回托管数组中 url 的位置，但以 String 形式返回，以便与发现的那些位置区分开来。插入；否则，返回一个整数 (Fixnum)，告诉 url 应位于何处以保持数组有序。

但请注意，我使用 Array#insert 来在指定位置添加元素。我的直觉告诉我，这种方法会将插入点后的所有元素向后移动一步，这可能会导致严重的性能下降。 Array 模块不在标准库中，它是 Ruby 的固有数据类型，所以我不知道我是否正确。

也许用于托管此类任务的数据结构太天真了。 那么任何人都可以分享一件很棒的事情吗？

Answer 1

如果，正如 Phrogz 建议的那样，您确实设法获得 370GB 内存，或者您意识到实际上不需要存储那么多 URL，那么您可能需要考虑使用 SortedSet。

Answer 2

您可能想看看越来越多的开源 NoSQL 解决方案，包括 MongoDB、Cassandra、Kyoto Cabinet 或 Redis。

MongoHQ 为 MongoDB 提供免费托管服务。 RedisToGo 为 Redis 提供免费托管服务。两者都有非常易于使用的 Ruby 绑定。我都用过并且推荐它们。

我听说过有关 Cassandra 和京都橱柜的好消息，但尚未在任何生产应用程序中使用它们。