关于Entry结构设计问题的追加
之前的设计见 版权Entry数据结构设计
这里再追加几个问题。
问题0、 如果使用 map
行不行?
如果使用方案一配合方案三,通过 map 来处理数据,然后再转换成数组。 还是2个问题:
1) account 很冗余。
2)每次更新数据都需要构建 key,(account + type),如果N多条记录,每次都要构建 N 次,这明显是不可取的。
问题1、 如果使用方案2,怎么处理一对多的问题,即一个账号对应多条记录。 如:
Account_A -> Entry1
Account_A -> Entry2
.
.
.
Account_A -> EntryN
首先,如果是这样的需求,更能反映出方案1、3不可取,大量的冗余和key构建。
这里依然使用方案2不矛盾,只不过 Role 中的 index 从 uint32_t 变为 vector, 里面记录该 Account 所属的Entry的Index。 如:
struct Role {
Account account;
std::vector<std::uint32_t> indexes;
};
Role r{account, {0,3,7}};
问题2、如果问题一可以解决,那怎么处理 index = 3 中的数据?
这个也好说,其实Entry是类似 type(类似于key), data 这样的结构,每个 Index 对应的数据是不一样的,从该Account的indexes中遍历即可获取到指定的数据。 此处的遍历跟方案1、3中构建所有的key,那肯定不是一个数量级的,甚至可以忽略不计。
问题3、如果中间一个数据要删除了,该怎么办?
这就是数组的特性了,最坏的情况,是第0号元素被删除,这时候需要所有的数据前移,同时还需要更新 Role 结构中的 indexes 索引,这个是避免不了的。 考虑到需求,删除操作是个很低频率的操作,并不会造成大面积的系统负担,所以也是可以接收的。
问题4、如果删除了,怎么更新数据?
这个涉及到2个结构,Entry列表和indexes结构,分3步走:
第一步: 删除 Account 的 indexes 中的数据,比如 index = 3 的数据要被删除, 则从 indexes 中删除 value = 3 的数据。
第二步: 然后,更新所有剩下的 index , 大于 3 的 index 相应的 -1 操作,因为这些是要移动的,小于3的不操作。
第三步: 移动 Entry 数组中的数据,比如 index = 3 的entry, 大于 3 的index 直接覆盖移动到前一个 index, 依次完成。
时间复杂度N, 空间复杂度1,至此更新结束。
问题5、如果数据返回给中间层,把数组打乱了,那么显示给上层的数据,对应的 indexes 也不准确了,怎么办?
第一: 为什么要让中间层把数组打乱?肯定要让它按照我的逻辑返回数据。
第二: indexes 的设计也不是为了让上层应用看的,如果应用层想看他自己的提交数据信息,我可以直接返回给他。
Nothing