g*********s
发帖数: 1782 | 1 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
好？
最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
间都double了，虽然复杂度不变。
两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
也不太好定。
有没有dual-key binary search tree之类的数据结构呢？ |
f*******y
发帖数: 988 | 2 要我看单独设置一个id和name的lookup表，加一个按照id或者name的树
size
【在 g*********s 的大作中提到】
: 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
: 入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
: 好？
: 最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
: 间都double了，虽然复杂度不变。
: 两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
: 也不太好定。
: 有没有dual-key binary search tree之类的数据结构呢？
|
g*****g
发帖数: 34805 | 3 简单的数据库就很好用，做两个索引就得。
其实就是两个hashtable. 绝大多数情况下，
不应该考虑去实现自己的数据结构，这本身
就不符合OO的思想。
在一个量级上，应该先问的是性能够了吗，够了
就是够了。
size
【在 g*********s 的大作中提到】
: 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
: 入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
: 好？
: 最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
: 间都double了，虽然复杂度不变。
: 两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
: 也不太好定。
: 有没有dual-key binary search tree之类的数据结构呢？
|
f*******y
发帖数: 988 | 4 他可能是作业题
【在 g*****g 的大作中提到】
: 简单的数据库就很好用，做两个索引就得。
: 其实就是两个hashtable. 绝大多数情况下，
: 不应该考虑去实现自己的数据结构，这本身
: 就不符合OO的思想。
: 在一个量级上，应该先问的是性能够了吗，够了
: 就是够了。
:
: size
|
s******e
发帖数: 431 | 5 空间怎么会double呢？你只需要为数据分配一次空间，两个hash table, 或者BST都只
需要记录数据的地址就可以了。
查找还是一样的。唯一不同的就是插入和删除需要做两次。
size
【在 g*********s 的大作中提到】
: 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
: 入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
: 好？
: 最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
: 间都double了，虽然复杂度不变。
: 两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
: 也不太好定。
: 有没有dual-key binary search tree之类的数据结构呢？
|
