B- 트리 키의 값은 어디에 저장됩니까?

저는 약 10k 개의 문자열 데이터베이스를 저장하기 위해 B-Trees를 연구했습니다. 각각의 문자열은 고유 한 ID를 가지고있어서 내 역할을 할 수 있다고 생각합니다. 그러나 내가 본 모든 구현은 값이 아닌 B-Tree의 키만 표시합니다. B-Tree는 맵으로 동작 할 때 키에 값을 연결해야하지만 키가있는 트리 노드에 저장되었는지 여부는 이해할 수 없습니다. 예를 들어.B- 트리 키의 값은 어디에 저장됩니까?

 ||key3| |key6|| 
    /  |   \ 
    / ||key4| |key5|| \ 
/      \ 
||key1| |key2||   ||key7| |key8||

 ||k3,v3| |k6,v6|| 
    /  |   \ 
    / ||k4,v4||k5,v5|| \ 
/      \ 
||k1,v1| |k2,v2||   ||k7,v7| |k8,v8||

나는 방법과 위치 값이 저장되어 모르겠습니다.

출처

2017-10-02 djay

모든 단일 노드에서 키와 함께 내부 및 리프 모두.

B + -Tree에서 모든 키는 리프 노드에서 사용할 수 있습니다. 따라서 리프 노드를 분할하는 경우 키를 부모 노드로 푸시하고 값을 유지할 수 있습니다. 그러나 B- 트리에서는 키가 반복되지 않으므로 내부 노드에 값을 가져야합니다.

키 - 값 맵을 사용하여 트리 특정 기능에 대한 키를 반복 할 수 있습니다. 키를 정렬 된 상태로 유지해야하므로 java의 TreeMap 또는 C++의 간단한 std :: map과 같은 정렬 된 맵을 사용해야합니다. (파이썬에는 표준 라이브러리에있는 것과 같은 것이 없습니다.) 또한 노드를 쉽게 분할하고 새로운 노드로 물건을 밀어 넣는 데 도움이됩니다.

출처

2017-10-02 14:21:19

그래서 10K 문자열 집합을 저장하려면 각 집합의 단어가 약 10 개이고 단어 중 하나가 고유 ID이고 두 번째 표현이 B- 트리를 작성하는 것이 맞습니까? 네, 정렬 된 구현을 기대하고 있습니다. 노드 내부의 SortedHashMap을 사용하여 키를 저장할 수 있습니까? 주 메모리가 아닌 파일과 같은 외부 메모리에 저장된 정보를 B-Tree에 저장하는 것을 이해하기 위해 시각화를 지적 할 수 있습니까? – djay

IMO, 2 번째 표현이 정확합니다. SortedHashMap에 대해 들어 보지 못했습니다. 무슨 말을하고 있습니까? 내가 아는 한, 해시 맵을 정렬하는 것은 불가능합니다. 시각화를 위해, https://www.cs.usfca.edu/~galles/visualization/BTree.html. 우리는 그것을 사용하여 배웠습니다. –

SortedHashMap에 의해 나는 B-Tree 노드가 정렬 된 순서로 키를 저장할 수 있는지 의심 스럽습니다. 오름차순이지만 20 이상의 길이를 갖는 긴 정수이기 때문에 해싱을 수행하는 데 키가 필요합니다. TreeMap을 보면서 다른 것을 보았습니다. 나는 해싱을 제외하고 전에 말했다. – djay

B- 트리 키의 값은 어디에 저장됩니까?

답변

관련 문제