存储整数范围的数据结构，查询范围和修改范围 [英] Data Structure to store Integer Range , Query the ranges and modify the ranges
问题描述
我们需要维护 mobileNumber 及其在内存中的位置.挑战在于我们有超过 500 万用户并且存储每个用户的位置就像 500 万条记录的哈希图.为了解决这个问题，我们必须处理范围
We need to maintain mobileNumber and its location in memory. The challenge is that we have more than 5 million of users and storing the location for each user will be like hash map of 5 million records. To resolve this problem, we have to work on ranges
我们获得了一系列电话号码，例如
We are given ranges of phone numbers like
range1 start="9899123446" end="9912345678" location="a"
range1 start="9899123446" end="9912345678" location="a"
range2 start="9912345679" end="9999999999" location="b"
range2 start="9912345679" end="9999999999" location="b"
一个号码只能属于一个位置.
A number can belong to single location only.
我们需要一个数据结构来将这些范围存储在内存中.
We need a data structure to store these ranges in the memory.
它必须支持两个功能
- findLocation(Integer number) 它应该返回位置名称属于哪个号码
- changeLocation(整数，字符串范围).它将 Number 的位置从旧位置更改为新位置
这完全在内存设计中.
我打算使用树结构，每个节点都包含( startofrange 、 endofrange 、location).我将按排序顺序保留节点.我还没有完成任何事情.主要问题是——当第二个改变位置的函数被调用时，说 9899123448 位置到 b
I am planning to use tree structure with each node contains ( startofrange , endofrange ,location). I will keep the nodes in sorted order. I have not finalized anything yet. The main problem is-- when 2nd function to change location is called say 9899123448 location to b
range1 节点应该拆分为 3 个节点第一个节点 (9899123446,9899123447,a)第二个节点(9899123448,9899123448,b) 第三个节点(9899123449,9912345678,a).
The range1 node should split to 3 nodes 1st node (9899123446,9899123447,a)
2nd node (9899123448,9899123448,b) 3rd node (9899123449,9912345678,a).
请建议合适的方法提前致谢
Please suggest the suitable approach Thanks in advance
推荐答案
通常您可以使用专门的数据结构来存储范围并实现查询，例如间隔树.
Normally you can use specialized data structures to store ranges and implement the queries, e.g. Interval Tree.
但是，由于电话号码范围不重叠，您可以将范围存储在标准的基于树的数据结构中 (二叉搜索树、AVL 树、红黑树，B 树，都可以工作)仅按 [begin] 排序.
However, since phone number ranges do not overlap, you can just store the ranges in a standard tree based data structure (Binary Search Tree, AVL Tree, Red-Black Tree, B Tree, would all work) sorted only by [begin].
对于findLocation(number)，使用相应的树搜索算法找到第一个[begin]值小于该数字的元素，检查其[end]值并验证该数字是否在该范围内.如果找到匹配，则返回位置，否则数字不在任何范围内.
For findLocation(number), use corresponding tree search algorithm to find the first element that has [begin] value smaller than the number, check its [end] value and verify if the number is in that range. If a match if found, return the location, otherwise the number is not in any range.
对于 changeLocation() 操作:
For changeLocation() operation:
- 找到包含数字的旧节点
- 如果在步骤 1 中找到现有节点，则将其删除并插入新节点
- 如果找不到现有节点，则插入一个新节点并尝试将其与相邻节点合并.
我假设您使用相同的操作来简单地添加新节点.
I am assuming you are using the same operation for simply adding new nodes.
更实际的做法是，您可以将所有条目存储在一个数据库中，并在 [begin] 上建立索引.
More practically, you can store all the entries in a database, build an index on [begin].
这篇关于存储整数范围的数据结构，查询范围和修改范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
