범위의 값을 빠르게 검색

geoip 데이터베이스가 IPrangeStart, IPrangeEnd, country 인 것으로 가정 해 봅시다. 등범위의 값을 빠르게 검색

#for, example 
1.1.1.1:2.2.2.2:US 
3.3.3.3:4.4.4.4:DE

는

이 데이터베이스는 문자열을 많이 가지고 있지만,이 모든 데이터를 할 수있는 완벽하게 맞는 메모리 (200-500Mb에 대한). 이제 우리는 ip로 국가를 찾아야합니다. 어떤 데이터 구조가 가장 적합합니까 (모든 IP를 int로 전송할 것입니까?).

출처

2014-06-19 Kirzilla

메모리에 4 차원 배열을 만들어 0.0.0.0에서 255.255.255.255 사이의 모든 값을 유지할 수 있습니다. 내 계산에 따르면 약 8GB의 메모리가 필요하지만 검색 시간이 가장 빠릅니다. –

범위 시작 값으로 정렬 된 배열을 사용하면 간단한 2 진 검색으로 적절한 범위를 찾을 수 있습니다. 얼마나 많은 주소 범위를 사용하고 있는지 알지 못하지만, 백만 범위가 있더라도 이진 탐색은 최대 20 개의 프로브를 필요로합니다. 당신은 쉽게 초당 수만 건의 조회를 할 수 있습니다.

다른 옵션은 segment tree이지만 겹치는 간격이 없으므로이 상황에서 특히 유용하지는 않습니다.

출처

2014-06-19 16:31:11

범위의 값을 빠르게 검색

답변

관련 문제