문자열의 외부 색인을 효율적으로 저장하십시오.

Question

디스크에 의이라는 n 개의 객체가있는 커다란 컬렉션이 있고 각각 가변 크기 문자열이 있다고 가정 해보십시오. 일반 문자열 비교를 통해 해당 개체의 인덱스를 만드는 효율적인 방법에 대한 일반적인 관행은 무엇입니까? 색인에 전체 문자열을 저장하는 것은 크기와 I/O에 장기간 소요되는 경우에는 매우 어려울 수 있지만 디스크의 참조 만 저장하면 대기 시간이 길기 때문에 좋은 아이디어는 아닙니다.

tries과 함께 B-Tree와 유사한 디자인을 사용하려고 생각했지만이 방법을 사용하여 데이터베이스 구현을 찾을 수 없습니다. 사실, 주요 데이터베이스가 문자열에 대한 색인을 구현하는 방법을 찾기가 어렵습니다 (SQL 수준의 정보에 대한 방대한 결과에서 손실 될 수 있음).

TIA!

EDIT : "큰 문자열로 저장된 개체를 효율적으로 외부 정렬 및 검색"에서 "문자열의 외부 색인을 효율적으로 저장"으로 제목이 변경되었습니다.

Answer 1

"접두사 B- 트리"또는 "간단한 접두사 B- 트리"가 여기 유용 할 것입니다.

"간단한 접두어 B- 트리"는 조금 더 간단합니다. 접두사 내에서 중복성을 제거하지 않고 두 항목을 구분하는 가장 짧은 접두어를 저장하는 것 (예 : '천문학'과 '방위각' 'as'와 'az'는 중복되지만 'a'는 중복되지 않도록하십시오.)

"접두사 B- 트리"는 사용자가 설명한 것과 유사합니다. 즉, 트리와 유사하지만 주로 디스크에 저장 될 때 좋은 특성을 제공하는 B- 트리 구조입니다. 그럼에도 불구하고 인덱스를 구성하는 접두어 내의 중복성을 제거 (대부분)하려고합니다.

다른 질문이 있습니다. 순서대로 레코드를 트래버스해야합니까, 아니면 지정된 레코드를 빨리 찾아야합니까? 후자가 적절한 경우 확장 가능 해시를 대신 사용할 수 있습니다. 확장 가능한 해싱은 수십 년 동안 (다양한 형태로) 존재 해 왔으며 여전히 잘 작동합니다. 일반적인 아이디어는 매우 간단합니다 : 문자열을 해시하여 고정 된 길이의 키를 만든 다음 고정 길이의 의사 키의 일종의 트리를 만듭니다. (거의) 해시와 마찬가지로 충돌을 처리 할 준비가되어 있어야합니다. 다른 해시 테이블과 마찬가지로 해싱 및 충돌 해결의 세부 사항은 다양합니다 (메모리 상 해싱과 같이 확장 가능한 해시는별로 중요하지 않지만).

실제 사용과 같이, 주요 DBMS 및 DBMS 계열 시스템은 위의 모든 것을 사용합니다. B- 트리 변형은 범용 DBMS 시장에서 가장 일반적 일 수 있습니다 (예 : Oracle 또는 MS SQL Server).확장 가능한 해싱은 많은 수의 특수 제품 (예 : Lotus Domino Server)에서 사용됩니다.

Answer 2

개체로 무엇을하고 있습니까?

많은 수의 동시 요청을 처리하기 위해 대기 시간이 짧은 대형 시스템을 실행중인 경우 개체를 데이터베이스에 저장하고 정렬 및 인덱싱을 처리해야합니다. 이것은 처음부터 B-tree를 구현하는 것보다 훨씬 간단 할 수 있으며 버그가있을 수도 있습니다.

DBMS에도 캐싱과 다양한 기능이있어 사용자의 삶을 편하게 만듭니다.

Answer 3

원하는 것을 시작으로 시작하십시오. 정렬하거나 색인을 생성 하시겠습니까? 정렬은 디스크의 항목 중 적어도 일부를 이동해야 할 수 있지만 인덱싱을 사용하면 항목을 그대로 둘 수 있습니다.

정말로의 경우 Knuth의 "The Art of Computer Programming" 볼륨 3은 원하는대로 자세하게 정렬하고 검색 할 수 있습니다.