나는 솔루션에 대한 시도를하기 위해 질문과 관련된 게시물을 읽는 데 두시간을 보냈지 만, 한 번 생각해 볼 때 성공하지 못했습니다.파일 검색을위한 최적의 온 디스크 데이터 구조?
그래서 여기에 : 나는 특정 단어가 파일에 존재 하는지를 검색하기 위해 어떤 데이터 구조를 사용할 것인지 한 번 인터뷰에서 질문을 받았다. 이 파일은 또한 메모리에 적합하지 않을 정도로 충분히 크고 면접자는 실제로 디스크상의 솔루션을 찾고있었습니다.
B-Tree는 디스크상의 데이터 구조입니까?
이진 검색 트리는 메모리 내 데이터 구조입니까?
정말 두 개의 서로 다른 가능한 질문이 여기에 있습니다 :
는 대규모 파일을 감안할 때, 단어가 파일에있는 경우 단어는 어떻게 확인합니까?
주어진 대용량 파일의 경우 파일에 임의의 단어가 있는지를 효율적으로 확인할 수 있도록 색인을 어떻게 작성합니까?
첫 번째 문제는 Boyer-Moore와 파일을 통한 선형 검색으로 효율적으로 해결됩니다. 한 번만 검색하는 경우 색인을 작성하는 것은 완전한 시간 낭비입니다.
두 번째 문제에 관해서는 면접관이 정말로 B-Trees를 밀고있는 것처럼 들립니다.
아마, 그게 내가 그에게 너무 말했지 :) – user183037
둘 다 단지 데이터 구조이며 디스크에 있거나 메모리에있을 수 있습니다. 사용 방법에 따라 다릅니다.
btw, B- 나무는 디스크 구조가 필요함에 따라 동기 부여되었습니다. 이진 탐색 트리는 B- 트리의 특별한 경우 일뿐입니다.
@Moron (lol!) - 데이터 구조를 디스크 또는 메모리에서 사용할 것인지 어떻게 지정합니까? (그것이 매우 순진한 질문이라면 유감스럽게 생각합니다!) – user183037
@user : 설정 매개 변수가 아닌 것 같습니다! 디스크에 데이터 구조를 저장하는 데 필요한 것이 무엇인지 고려해야합니다. 예를 들어, 이진 검색 트리 (또는 심지어 Btree)에서 다른 노드에 대한 포인터는 파일 내에서 찾는 오프셋으로 변환 될 수 있습니다. –
오! 알았어. 고마워. – user183037
디스크 공간의 한 노드에 한 노드를 매핑하는 데이터 구조를 사용하려고합니다. 이렇게하면 디스크 활동이 최소화됩니다.
B- 트리가 종종이 용도로 사용되기 때문입니다. http://en.wikipedia.org/wiki/B-tree, 특히 "정렬 된 파일 검색 시간"절을 참조하십시오.
그래서 B- 트리가이 목적을위한 최상의 데이터 구조입니까? (그냥 확인) – user183037
"디스크에 B-tree가 있습니까?"라는 질문을 받았습니다. "이진 트리가 디스크에 있습니까?" 당신이 무언가를 쓰는 것 같지만 실제로 뭔가 다른 것을 의미합니다 :-) 놀랍게도,이 질문을 읽는 사람들은 당신이 정말로 원하는 것을 이해 한 것 같습니다! –
내가 혼란스러워하면 미안합니다. 제가하려는 것은 상황을 구축하고 질문을하는 것입니다. 나는 실제로 들어 본 적이없는 데이터 구조가 있는지 알아보고 면접관에게 주어진 답변이 맞는지 알아보기 위해 조사를 진행했습니다. :) – user183037