B 트리와 B+ 트리의 차이점은 무엇입니까?
b-tree에서는 내부 노드와 리프 노드에 키와 데이터를 모두 저장할 수 있지만, b+tree에서는 리프 노드에만 데이터를 저장해야 합니다.
b+ 트리에서 위의 작업을 수행하는 것에 이점이 있습니까?
직관적으로 훨씬 더 빠른 것처럼 보이는데 어디서나 b+ 트리 대신 b-트리를 사용하는 것은 어떨까요?
왜 b+ 트리에 키(데이터)를 복제해야 합니까?
아래 이미지는 B+트리와 B트리의 차이점을 보여주는 데 도움이 됩니다.
B+ 트리의 장점:
- B+ 트리에는 내부 노드와 관련된 데이터가 없기 때문에 메모리 페이지에 더 많은 키가 들어갈 수 있습니다.따라서 리프 노드에 있는 데이터에 액세스하기 위해 필요한 캐시 누락이 줄어듭니다.
- B+ 트리의 리프 노드는 연결되어 있으므로 트리의 모든 객체를 전체 스캔하려면 모든 리프 노드를 한 번의 선형 통과만 필요합니다.반면에 B 트리는 트리의 모든 레벨의 횡단이 필요합니다.이 전체 트리 횡단은 B+ 잎의 선형 횡단보다 더 많은 캐시 미스를 수반할 가능성이 있습니다.
B 트리의 장점:
- B 트리에는 각각의 키를 가진 데이터가 포함되어 있기 때문에 자주 액세스하는 노드는 루트에 더 가까이 위치할 수 있으므로 보다 신속하게 액세스할 수 있습니다.
B+ 트리의 주된 장점은 데이터에 대한 포인터를 제거함으로써 다른 노드에 대한 포인터를 더 많이 포장할 수 있도록 하여 팬아웃을 증가시키고 잠재적으로 트리의 깊이를 감소시킬 수 있다는 것입니다.
단점은 내부 노드에서 일치하는 것을 발견했을 때 조기 종료가 발생하지 않는다는 것입니다.하지만 두 데이터 구조 모두 엄청난 팬아웃을 가지고 있기 때문에 어쨌든 매치의 대부분은 리프 노드에 있을 것이므로 평균적으로 B+ 트리의 효율성이 더 높아집니다.
B+Tree는 터미널 노드가 연결된 목록을 구성하므로 트리가 인덱스하는 모든 데이터를 보는 것처럼 전체 검색을 수행하는 데 훨씬 쉽고 성능이 높습니다.B-Tree로 전체 스캔을 수행하려면 모든 데이터를 찾기 위해 전체 트리 순회를 수행해야 합니다.
반면에 B-트리는 탐색(키별로 특정 데이터를 검색)을 수행할 때, 특히 트리가 RAM 또는 기타 비블록 스토리지에 있을 때 더 빨라질 수 있습니다.트리에서 일반적으로 사용되는 노드를 상승시킬 수 있으므로 데이터를 가져오는 데 필요한 비교가 줄어듭니다.
- B 트리에서 검색 키와 데이터는 내부 또는 리프 노드에 저장됩니다.그러나 B+트리 데이터는 리프 노드에만 저장됩니다.
- 모든 데이터가 리프 노드에서 발견되기 때문에 B+ 트리의 전체 스캔은 매우 쉽습니다.B 트리를 전체 스캔하려면 전체 순회가 필요합니다.
- B 트리에서는 리프 노드나 내부 노드에서 데이터를 찾을 수 있습니다.내부 노드 삭제는 매우 복잡합니다.B+ 트리에서는 리프 노드에서만 데이터가 발견됩니다.리프 노드 삭제는 쉽습니다.
- B 트리의 삽입은 B+ 트리보다 복잡합니다.
- B+ 트리는 중복 검색 키를 저장하지만 B 트리는 중복 값이 없습니다.
- B+ 트리에서는 리프 노드 데이터가 순차적 링크 리스트로 정렬되지만 B 트리에서는 링크 리스트를 사용하여 리프 노드를 저장할 수 없습니다.많은 데이터베이스 시스템의 구현은 B+ 트리의 구조적 단순성을 선호합니다.
데이터베이스 시스템 개념의 예제 5th
+
B-
아메트, 아메트
여러분이 놓치고 있는 중요한 점 중 하나는 이 섹션에서 설명한 데이터와 포인터의 차이라고 생각합니다.
포인터 : 다른 노드를 가리키는 포인터입니다.
데이터 :- 데이터베이스 인덱스의 맥락에서 데이터는 다른 곳에 있는 실제 데이터(행)에 대한 또 다른 포인터일 뿐입니다.
따라서 B 트리의 경우 각 노드에는 3개의 정보 키, 키와 관련된 데이터에 대한 포인터 및 하위 노드에 대한 포인터가 있습니다.
B+ 트리에서 내부 노드는 자식 노드에 키와 포인터를 유지하고 리프 노드는 관련 데이터에 키와 포인터를 유지합니다.따라서 지정된 크기의 노드에 대해 더 많은 수의 키를 허용할 수 있습니다.노드의 크기는 주로 블록 크기에 따라 결정됩니다.
노드당 키가 더 많다는 장점은 위에서 잘 설명하였으니 타이핑 노력을 아끼겠습니다.
B+ 트리는 특히 블록 기반 스토리지(예: 하드 디스크)에 적합합니다.이를 염두에 두고 몇 가지 이점을 얻을 수 있습니다. 예를 들어 (제 머리 위에서):
high fanout / low depth: 데이터에 접근하기 위해 더 적은 블록을 확보해야 함을 의미합니다.데이터가 포인터들과 섞이면, 각각의 읽기는 더 적은 포인터들을 가지게 되고, 따라서 데이터를 얻기 위해 더 많은 시도가 필요합니다.
단순하고 일관된 블록 저장: 내부 노드는 N개의 포인터를 가지고 있고 다른 것은 없고 리프 노드는 데이터를 가지고 있고 다른 것은 없습니다.파싱, 디버그, 재구성까지 쉽게 해줍니다.
키 밀도가 높다는 것은 상위 노드가 거의 확실하게 캐시에 저장되어 있다는 것을 의미합니다. 많은 경우 모든 내부 노드가 빠르게 캐시되므로 데이터 액세스만 디스크로 이동하면 됩니다.
"훨씬 더 빨리"를 정의합니다.점근적으로 보면 둘은 거의 같습니다.차이점은 보조 스토리지를 사용하는 방법에 있습니다.B-tree와 B+tree에 대한 위키피디아 기사들은 꽤 신뢰할만해 보입니다.
B+ Tree에서는 포인터만 내부 노드에 저장되므로, 포인터의 크기가 (데이터+키를 모두 저장하는) B Tree의 내부 노드보다 상당히 작아집니다.따라서 B+ 트리의 인덱스를 단일 디스크 읽기로 외부 저장소에서 가져와 대상의 위치를 찾을 수 있습니다.B 트리의 경우, 각각의 의사 결정 과정마다 디스크 읽기가 필요합니다.내 주장을 분명히 했길 바래요! :)
**
B-Tree의 가장 큰 단점은 키를 순차적으로 이동하는 것이 어렵다는 것입니다.B+ Tree는 B-Tree의 빠른 랜덤 액세스 속성을 유지하는 동시에 빠른 순차 액세스를 가능하게 합니다.
** ref: C// 작성자를 사용한 데이터 구조:아라로 엠 테넨바움
B-tree와 B+tree의 주된 차이점은 B-tree가 검색 키 값의 중복 저장을 제거한다는 것입니다.B-tree에서는 검색키가 반복되지 않기 때문에 해당 B+tree 인덱스보다 적은 수의 트리 노드를 사용하여 인덱스를 저장하지 못할 수 있습니다.그러나 리프가 아닌 노드에 나타나는 검색 키는 B-tree의 다른 어디에도 나타나지 않기 때문에 리프가 아닌 노드에 있는 각 검색 키에 대한 추가 포인터 필드를 포함할 수 밖에 없습니다.반복이 발생하지 않고 큰 인덱스에 사용할 수 있기 때문에 B-트리에 대한 공간 이점입니다.
한 가지 예를 들어, 행당 데이터가 방대한 표를 사용할 수 있습니다.이는 개체의 모든 인스턴스가 Big임을 의미합니다.
여기서 B 트리를 사용하면 대부분의 시간이 데이터로 페이지를 스캔하는 데 사용되므로 아무 소용이 없습니다.데이터베이스에서 객체 데이터 검색을 피하기 위해 B+ 트리를 사용하는 이유입니다.
B+ 트리는 키와 데이터를 구분합니다.
하지만 데이터 크기가 작으면 B 트리가 하는 키로 저장할 수 있습니다.
B+tree는 나무의 뿌리에서 잎으로 가는 모든 경로가 동일한 길이이고, 나무의 각 비잎 노드는 [n/2]에서 [n] 사이의 자식을 가지며, n은 특정 트리에 대해 고정됩니다.인덱스 페이지와 데이터 페이지가 포함되어 있습니다.이진 트리에는 부모 노드당 두 개의 자식만 있습니다. B+ 트리에는 각 부모 노드에 대해 가변적인 자식 수가 있습니다.
B+ 트리의 한 가지 가능한 용도는 트리가 너무 커져서 사용 가능한 메모리에 맞지 않는 상황에 적합하다는 것입니다.따라서 일반적으로 여러 I/O를 수행할 것으로 예상됩니다.
B+ 트리가 실제로 메모리에 들어갈 때에도 사용되는 경우가 종종 있는데, 그러면 캐시 관리자가 이 트리를 영구적으로 보관할 수도 있습니다.그러나 이는 일반적인 경우가 아닌 특수한 경우이며 캐싱 정책은 B+ 트리 유지보수와는 별개의 것입니다.
또한 B+ 트리에서 리프 페이지는 연결된 목록(또는 이중 연결된 목록)에서 함께 연결되며, 이는 (범위 검색, 정렬 등을 위해) 횡단을 최적화합니다.따라서 포인터의 수는 사용되는 특정 알고리즘의 함수입니다.
언급URL : https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees
'programing' 카테고리의 다른 글
| C: 문자열을 연결하는 가장 빠르고 좋은 방법은 무엇입니까? (0) | 2023.10.30 |
|---|---|
| 열별로 그룹화된 것을 색인으로 만들지 않고 그룹화하는 판다. (0) | 2023.10.30 |
| ar의 "rcs" 옵션은 무엇을 합니까? (0) | 2023.10.30 |
| PL/SQL 전용 VARCHAR232767 바이트를 모두 만들지 않는 이유는 무엇입니까? (0) | 2023.10.30 |
| C/C++ 서로 다른 플랫폼에서 동적 연결은 어떻게 작동합니까? (0) | 2023.10.30 |