通过最大值和ID检索的最佳数据结构? [英] Best data structure to retrieve by max values and ID?

问题描述

我有很多固定大小的记录.每个记录都有很多字段，其中包括ID和Value.我想知道哪种数据结构最好，这样我就可以

I have quite a big amount of fixed size records. Each record has lots of fields, ID and Value are among them. I am wondering what kind of data structure would be best so that I can

1. 通过ID(唯一)快速找到记录，

1. locate a record by ID(unique) very fast,

列出具有最大值的100条记录.

list the 100 records with the biggest values.

最大堆似乎可行，但远非完美；您有更聪明的解决方案吗?

Max-heap seems work, but far from perfect; do you have a smarter solution?

谢谢.

推荐答案

混合数据结构最有可能是最好的.为了通过ID进行有效查找，良好的结构显然是哈希表.为了支持top-100迭代，最大堆或二叉树是一个很好的选择.插入和删除时，只需对两个结构都进行操作.如果迭代次数的100是固定的，则迭代会频繁发生，并且插入/删除不会严重倾斜到前100名，只需将前100名保留为有排序的数组，并溢出到最大堆即可.这不会改变结构的big-O复杂性，但是对于迭代情况，它将提供非常好的恒定因子加速.

A hybrid data structure will most likely be best. For efficient lookup by ID a good structure is obviously a hash-table. To support top-100 iteration a max-heap or a binary tree is a good fit. When inserting and deleting you just do the operation on both structures. If the 100 for the iteration case is fixed, iteration happens often and insertions/deletions aren't heavily skewed to the top-100, just keep the top 100 as a sorted array with an overflow to a max-heap. That won't modify the big-O complexity of the structure, but it will give a really good constant factor speed-up for the iteration case.

这篇关于通过最大值和ID检索的最佳数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！