数据结构存储整数范围,查询范围和修改范围

Question

我们需要维护mobileNumber及其在内存中的位置.挑战在于我们拥有超过500万用户,并且每个用户的存储位置将像500万条记录的哈希地图.要解决此问题,我们必须处理范围

我们给出了电话号码的范围

• range1 start ="9899123446"end ="9912345678"location ="a"

• range2 start ="9912345679"end ="9999999999"location ="b"

数字只能属于单个位置.

我们需要一个数据结构来将这些范围存储在内存中.

它必须支持两个功能

1. findLocation(整数)它应该返回数字所属的位置名称
2. changeLocation(整数,字符串范围).它将Number的位置从旧位置更改为新位置

这完全是在内存设计中.

我打算使用树结构,每个节点包含(startofrange,endofrange,location).我将按节目顺序保留节点.我还没有完成任何事情.主要问题是 - 当第二个改变位置的功能被称为9899123448位置到b时

range1节点应拆分为3个节点第1个节点(9899123446,9899123447,a) 第2个节点(9899123448,9899123448,b)第3个节点(9899123449,9912345678,a).

请提出合适的方法,提前致谢

Answer 1

通常,您可以使用专门的数据结构来存储范围并实现查询,例如Interval Tree.

但是,由于电话号码范围不重叠,您只需将范围存储在基于标准树的数据结构(二叉搜索树,AVL树,红黑树,B树,都可以工作)中,仅按[begin]排序.

对于findLocation(数字),使用相应的树搜索算法查找[begin]值小于该数字的第一个元素,检查其[end]值并验证该数字是否在该范围内.如果找到匹配项,则返回该位置,否则该数字不在任何范围内.

对于changeLocation()操作:

1. 找到包含该编号的旧节点
2. 如果在步骤1中找到现有节点,则删除它并插入新节点
3. 如果未找到现有节点,请插入新节点并尝试将其与相邻节点合并.

我假设您使用相同的操作来简单地添加新节点.

更实际的是,您可以将所有条目存储在数据库中,在[begin]上构建索引.

Answer 2

首先range= [ begin; end; location]

使用两种结构：

• 存储 s 的range排序begin数组
• 通过s访问ends 和s的哈希表locationbegin

应用以下算法：

1. 使用二分查找查找“最近的较小”值 obbegin
2. 使用哈希表来查找end和location查找begin