设计DNS服务器中cache的数据结构。
要求设计一个DNS的Cache结构,要求能够满足每秒5000以上的查询,满足IP数据的快速插入,查询的速度要快。(题目还给出了一系列的数据,比如:站点数总共为5000万,IP地址有1000万,等等)
回答:
DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节(估计值),每个IP为4个字节,所以Cache的每个条目需要大概30个字节。
总共50M个条目,所以需要1.5G个字节的空间。可以放置在内存中。(考虑到每秒5000次操作的限制,也只能放在内存中。)
可以考虑的数据结构包括hash_map,字典树,红黑树等等。
核心思想:估算、哈希