该程序使用kd-B Tree(结合了kd-trees和B-trees的特性)来存储商家。 因为商家列表理论上是无限的,更简单的 kd-tree 是不可接受的,因为它不允许动态插入。 我还修改了 kd-B 树,以允许我们在查询时按类别进行过滤。 如果有太多条目无法放入内存,则可以轻松地将树更改为使用辅助存储。
我选择了 Ruby,以便可以轻松地将树包含到 RoR 或 Sinatra 项目中。 我还包括 rspec 测试以确保树正常运行。
参考
Robinson, John T.“KDB 树:大型多维动态索引的搜索结构”,卡内基梅隆大学,匹兹堡,1981 年。
2021-07-12 14:04:45
228KB
Ruby
1