T-tree 또는 B-tree

Question

T-tree 알고리즘은 this paper 에 설명되어 있습니다. T * -Tree는 범위 쿼리를 비롯하여 T 쿼리의 다른 모든 유용한 기능을 포함하여 쿼리 작업을보다 잘 활용할 수 있도록 T-tree에서 개선 된 기능입니다. -나무.
이 알고리즘은이 백서 "T * -tree : 실시간 응용 프로그램의 주 메모리 데이터베이스 색인 구조"에서 설명합니다.
이 연구 보고서에 따르면 T-Tree는 데이터 세트가 메모리에 들어갈 때 B-tree/B + 트리보다 빠릅니다. 이 문서에서 설명한대로 T-Tree/T * Tree를 구현하고 성능을 B-tree/B + tree와 비교했지만 B-tree/B + tree는 모든 테스트에서 T-Tree/T * Tree보다 성능이 뛰어납니다. 사례 (삽입, 삭제, 검색).
T-Tree는 메모리 내장 데이터베이스의 효율적인 인덱스 구조이며 Oracle TimesTen에서 사용했습니다. 그러나 나의 결과는 그것을 보여주지 않았다.
누군가가 그 이유를 알고 있거나 그것에 대해 의견이 있으면 그 사람 (또는 그 사람)의 의견을 듣는 것이 좋습니다.

Answer 1

T-trees는 AVL 트리 또는 B- 트리가 동일한 의미에서 기본적인 데이터 구조는 아닙니다. 그것들은 균형 잡힌 바이너리 트리의 해킹 된 버전 일 뿐이므로 적절한 성능을 제공하는 틈새 어플리케이션이있을 수도 있고 그렇지 않을 수도 있습니다.

예상되는 블록/페이지 전송 수와 캐시 지역성이라는 측면에서 볼 때이 사이트는 빈약 한 지역성으로 인해 끔찍한 고통을 겪습니다. 후자는 마지막 노드를 제외한 모든 노드 액세스에서 경계 값만 검색 키에 대해 검사되므로 모든 나머지는 페이지되지 않거나 아무 것도 캐시되지 않기 때문에 분명합니다.

일반적으로 B- 나무와 B + 나무의 탁월한 액세스 지역 (특히 메모리 성능 특성을 염두에두고 설계된 캐시 잊어 버림 및 캐시 인식 버전은 말할 것도 없습니다)과 비교하십시오.

비슷한 문제가 재조정에 있습니다. B- 트리 세계에서는 동시성 (잠금/래칭) 또는 그 부재와 같은 측면을 포함하여 원하는 상환 성능 특성을 달성하기 위해 B + 및 Blink로 시작하는 많은 변형이 개발되고 완성되었습니다. 따라서 대부분의 경우 단순히 외출하여 실적 프로필에 맞는 B-tree 변형을 찾거나 간단한 고전 B + 트리를 사용하여 확실한 결과를 얻을 수 있습니다.

T-trees는 비교 가능한 B-tree보다 복잡하며 성능면에서 전혀 제공하지 않는 것으로 보입니다. 일반적으로, 단일 레벨 메모리 '계층 구조' 수십 년 동안 사라졌습니다. 하드 디스크가 새로운 메모리 일뿐만 아니라 그 반대도 마찬가지이며 주 메모리는 이제 새로운 하드 디스크입니다. 나는. NUMA가 없더라도 주 메모리에서 캐시 계층으로 데이터를 가져 오는 데 드는 비용이 너무 많아 페이지 전송을 최소화하는 것이 좋습니다. 이는 정확하게 B- 트리와 그 변형이 수행하는 것이며 T- 트리는 그렇지 않습니다. 프로세서 코어에 가까워지면 캐시 라인 액세스/전송의 수가 중요하지만 그림은 동일하게 유지됩니다.

실제적으로 최적 인 이진 검색 아이디어를 취하여 메모리 계층 구조 (캐시)와 잘 작동하는 방식으로 검색 키를 배열하는 방법에 대해 생각해 보면 결국에는 B-tree처럼 멋지게 보입니다.

성능을 위해 프로그래밍하면 정렬 된 배열, B- 트리 및 해싱 사이의 삼각형에 어버이 거의 항상 위치합니다. 상대적으로 열악한 성능이 다른 고려 사항에도 불구하고 뒷좌석을 차지하고 키 수는 매우 적어서 2 백만 개를 초과하지 않는 경우 균형 잡힌 이진 트리만 경쟁력이 있습니다.