B + 트리의 일반적인 구현에서, 키는 고정 길이 (예 : 25 바이트)를 가질 수 있다고 가정 할 수 있습니다. 그런 다음 각 노드가 최소 키 수와 최대 키 수를 가져야한다고 정의 할 수 있습니다.가변 길이 키를 갖는 B + 트리
트리에서 가변 길이 키를 허용하려면 무엇을 수정해야합니까? 노드에 적어도 2 개의 키가 있어야한다고 말하면 삽입하려고하는 키가 너무 커서 노드를 보유하는 블록에 맞지 않습니다.
단순한 해결책은 값 대신 키를 포인터 (상대 연산자를 덮어 쓰는 형식으로 싸는 포인터)로 저장하는 것이지만 물론 B + 트리를 사용하는 지점의 일부인 지역을 손상시키는 것입니다.
즉, 항목이 클수록 항목이 메모리에 인접 해 있다는 것이 중요하지 않습니다. 거대한 항목은 동일한 페이지에 여러 페이지를 넣을 수는 없지만 하나의 캐시 페이지에도 맞지 않습니다.
또 다른 간단한 방법은 사용하는 모든 항목 유형에 충분히 큰 항목 메모리 유형 내에서 항목을 할당하기 위해 공용체 또는 배치를 새로 사용하는 것입니다. 항목 당 고정 된 바이트 수가 여전히 있지만 항목이 모든 바이트를 반드시 사용하는 것은 아닙니다.
작업을 수행하려면 가변 크기 노드가 필요할 수 있습니다. 물론 노드 내 데이터 구조를 어떻게 배열 하느냐에 따라 해당 노드로 작업하는 번거 로움이 있습니다. 예를 들어, 노드 내부에있는 항목 (힙에 별도로 할당되지 않은 항목)을 가리키는 경우, 노드 내에 작은 항목 - 포인터 배열을 가질 수 있습니다.
또한 노드를 변경할 때마다 노드를 재 할당해야 할 수 있습니다. 비록 당신이하고있는 일이 리 밸런싱이라 할지라도 한 노드에서 다른 노드로 거대한 아이템을 옮길 수 있습니다. 그리고 목적지 노드는 아이템을위한 슬롯이 없다는 의미에서 공간이 있습니다. 값.
의미로 각 노드는 크거나 작은 항목의 공간을 할당하거나 해제 할 수있는 미니 힙이 될 수 있지만 때로는 해당 미니 힙을 다른 힙으로 대체하기 위해 적절한 힙으로 돌아 가야합니다. 더 크거나 작은 것.
항목이 너무 크면 노드 내 지역이 아마도 관련성이 없다는 것을 다시 한번 언급 할 가치가 있습니다.
필자는 자신 앞에 메모리에 B + 스타일 다중 경로 트리를 구현했지만 필자는이 극단으로 갈 수 없었습니다.
해시 사용. 해시는 고정 된 크기의 키 표현입니다. 좋은 해싱 함수는 http://www.cse.yorku.ca/~oz/hash.html을 참조하십시오.
응? 트리에 해시 값을 저장할 수 없습니다. 두 개의 키가 같은 값으로 해시되면 어떻게됩니까? 나무에서 어떻게 찾을 수 있습니까? –
@ l19 : 물론 가능합니다. 다음 (링크 된 목록)에 대한 포인터가있는 키 - 값 쌍에 포인터를 추가하기 만하면됩니다. 특정 키를 검색 할 때 트리에서 해시를 찾은 다음 키를 비교하여 체인을 따라 이동합니다. – Philip
어떤 시점에서 B + 트리보다 빠른 해시 테이블을 사용할 수도 있습니다. B + 트리를 사용하는 주된 이유는 키의 두 값 (하위 쿼리) 사이의 항목을 추출하거나 모든 항목을 순서대로 나열 할 수 있어야한다는 것입니다. – Jules
there과 같은 오버플로 페이지에서 큰 키의 나머지 부분을 유지할 수 있습니다.
블록에서 두 개 이상 그룹화하지 않으면 B + 트리가 키를 효율적으로 처리하지 못합니다. 일반적으로 키의 크기는 적당합니다 (최대 백 바이트라고 추측합니다). – Inspired