[database] B 트리와 B + 트리의 차이점은 무엇입니까?
A의 B-나무 는 모두 저장할 수있는 내부 및 잎 노드의 키와 데이터를 하지만,에 ㄱ + 트리 당신은에 데이터를 저장해야 할 경우에만 리프 노드 .
b + 트리에서 위의 작업을 수행하면 이점이 있습니까?
직관적으로 훨씬 빠르기 때문에 어디에서나 b + 트리 대신 b- 트리를 사용하지 않겠습니까?
b + 트리에서 키 (데이터)를 복제해야하는 이유는 무엇입니까?
답변
아래 이미지는 B + 트리와 B 트리의 차이점을 보여줍니다.
B + 나무의 장점 :
- B + 트리에는 내부 노드와 관련된 데이터가 없으므로 메모리 페이지에 더 많은 키를 넣을 수 있습니다. 따라서 리프 노드에있는 데이터에 액세스하려면 캐시 누락이 덜 필요합니다.
- B + 트리의 리프 노드는 연결되어 있으므로 트리의 모든 객체를 전체 스캔하려면 모든 리프 노드를 통해 하나의 선형 패스 만 있으면됩니다. 반면에 AB 트리는 트리의 모든 레벨을 순회해야합니다. 이 전체 트리 순회에는 B + 리프의 선형 순회보다 더 많은 캐시 누락이 포함될 수 있습니다.
B 나무의 장점 :
- B 트리에는 각 키가있는 데이터가 포함되어 있으므로 자주 액세스하는 노드가 루트에 더 가까이있을 수 있으므로 더 빠르게 액세스 할 수 있습니다.
답변
B 트리보다 B + 트리의 주요 장점은 데이터에 대한 포인터를 제거하여 팬 아웃을 높이고 트리 깊이를 잠재적으로 줄임으로써 다른 노드에 대한 더 많은 포인터를 넣을 수 있다는 것입니다.
단점은 내부 노드에서 일치하는 것을 발견했을 때 초기 결과가 없다는 것입니다. 그러나 두 데이터 구조 모두 팬 아웃이 많으므로 대부분의 일치 항목이 리프 노드에 배치되어 평균 B + 트리가 더 효율적입니다.
답변
터미널 노드가 연결된 목록을 형성하기 때문에 트리가 인덱싱하는 모든 데이터를 살펴 보듯이 B + 트리는 전체 스캔을 수행하는 것이 훨씬 쉽고 성능이 뛰어납니다. B-Tree로 전체 스캔을 수행하려면 모든 데이터를 찾기 위해 전체 트리 순회를 수행해야합니다.
반면에 B- 트리는 트리가 RAM 또는 다른 비 블록 스토리지에 상주 할 때 키를 사용하여 특정 데이터를 찾는 경우 더 빠를 수 있습니다. 트리에서 일반적으로 사용되는 노드를 올릴 수 있으므로 데이터를 얻는 데 필요한 비교가 적습니다.
답변
- B 트리에서 검색 키와 데이터는 내부 또는 리프 노드에 저장됩니다. 그러나 B + 트리에서 데이터는 리프 노드에만 저장됩니다.
- 모든 데이터가 리프 노드에서 발견되므로 B + 트리의 전체 스캔이 매우 쉽습니다. B 트리의 전체 스캔에는 전체 순회가 필요합니다.
- B 트리에서 데이터는 리프 노드 또는 내부 노드에서 찾을 수 있습니다. 내부 노드 삭제는 매우 복잡합니다. B + 트리에서 데이터는 리프 노드에서만 발견됩니다. 리프 노드 삭제가 쉽습니다.
- B 트리에서의 삽입은 B + 트리보다 복잡합니다.
- B + 트리는 중복 검색 키를 저장하지만 B 트리는 중복 값이 없습니다.
- B + 트리에서 리프 노드 데이터는 순차적 링크리스트로 정렬되지만 B 트리에서 리프 노드는 링크 된리스트를 사용하여 저장할 수 없습니다. 많은 데이터베이스 시스템의 구현에서는 B + 트리의 구조적 단순성을 선호합니다.
답변
데이터베이스 시스템 개념의 예 5
B + 트리
해당 B- 트리
답변
“훨씬 빨리”정의하십시오. 무의식적으로 그들은 거의 같습니다. 차이점은 이들이 보조 스토리지를 사용하는 방법에 있습니다. B- 트리 및 B + 트리 에 대한 Wikipedia 기사는 매우 신뢰할 수 있습니다.
답변
Adegoke A, Amit
사람들이 누락 한 중요한 점은이 섹션에서 설명한 데이터와 포인터의 차이점이라고 생각합니다.
포인터 : 다른 노드를 가리키는 포인터.
데이터 :-데이터베이스 인덱스의 맥락에서 데이터는 다른 곳에 존재하는 실제 데이터 (행)에 대한 또 다른 포인터 일뿐입니다.
따라서 B 트리의 경우 각 노드에는 세 개의 정보 키, 키와 관련된 데이터에 대한 포인터 및 자식 노드에 대한 포인터가 있습니다.
B + 트리에서 내부 노드는 하위 노드에 대한 키와 포인터를 유지하고 리프 노드는 관련 데이터에 대한 키와 포인터를 유지합니다. 이것은 주어진 크기의 노드에 대해 더 많은 키를 허용합니다. 노드의 크기는 주로 블록 크기에 의해 결정됩니다.
노드 당 더 많은 키를 갖는 장점은 위에 설명되어 있으므로 입력 노력을 절약 할 수 있습니다.
