정렬 된 데이터에 인덱스 만들기

Question

줄 바꿈으로 분할 된 정렬 된 데이터가있는 텍스트 파일이 있습니다. 예를 들면 :

1. getStringByIndex (N) :의 n 번째 항목을 반환

   ...
abc123
abc124
abd123
abd124
abd125
...

   는 지금은 (적어도)을 지원해야 데이터 세트에 대한 인덱스를 만들려면 정렬 된 목록;

2. getIndexByString : 모든 항목에서 find, 해당 색인을 반환하거나 (발견되지 않으면 -1);

해싱 및 B- 트리와 같은 색인 생성 알고리즘을 읽었습니다. 여분의 아동용 필드가있는 B-Tree는 그렇게해야합니다. 그러나 데이 테셋이 정렬 되었기 때문에 모든 항목을 삽입하여 B-Tree를 작성하는 것보다 효과적인 솔루션이 있는지 궁금합니다.

Answer 1

데이터가 정렬되었으므로 작고 희소 한 데이터 하위 집합을 메모리에 유지함으로써 콘텐츠를 매우 빠르고 효율적으로 찾을 수 있습니다. 예를 들어 메모리에있는 모든 N 번째 요소를 저장하기로 결정했다고합시다. API를 효율적으로 초기화하려면이 스파 스 목록을 디스크의 별도 파일에 컴파일해야하므로 가져 오기 위해 100GB의 데이터를 스트리밍 할 필요가 없습니다.

이러한 용어 각각에 대해 용어가 시작되는 파일의 헤드를 기준으로 디스크 오프셋을 저장해야합니다.

getStringByIndex(n): 
     Get floor(n/N)-th string/offset pair from list 
     Seek offset position in index 
     Read/Skip n mod N strings, then return the next one 

    getIndexByString(s): 
     Binary search over sparse list in memory 
      Locate lower and upper bound string/offset pairs 
     If a string/offset pair is in the i-th position in our sparse list, 
      then the string itself is the (N x i)-th string in our index. 
      We can use this information to compute the return value 
     If the string we want isn't in memory: 
      Seek lower-bound offset in index 
      Read strings until we: 
       a) Find a match 
       b) Reach the high-bound offset 
       c) Reach a string which is lexicographically greater than the one we are looking for 
     Else 
      Just return the index for the matching string in our sparse list 

색인에서 문자열 폭을 고정하는 경우, 당신이 할 수있는 그런 다음, 당신은 할 수있어 모두가/메모리로 쌍을 상쇄하고이 개 요청의 구현은 간단하게 스파 스 목록을로드입니다 더 큰 최적화를하십시오.

이 알고리즘을 구현하면 'N'을 선택하는 데주의해야합니다. 디스크상의 한 위치에서 10 바이트를 읽는 비용은 같은 위치에서 10,000 바이트를 읽는 비용보다 훨씬 적습니다. 디스크 찾기의 오버 헤드이며 I/O 호출에서 들어오고 나가는 오버 헤드입니다. 가장 아프다.