7
b 트리 및 b + 트리는 리프에만 데이터를 저장합니까? 나는 그들이 내부 노드를 사용하여 필요한 데이터를 검색한다고 가정합니다.btrees 및 b + 나무는 리프에 데이터 만 저장합니까?
이 경우에도 모든 노드에 데이터가 저장됩니까?
A
답변
7
잎 이외의 노드 "기록"나무
- 포인터 (종류의 노드 "주소")를 포함 (또는 구현에 따라 마지막으로) 해당 노드의 레코드
이러한 비 리프 "레코드"는 키 순서로 나열되어 있기 때문에 비 리프 노드를 검색 (또는 이진 검색)하여 어느 노드가 다음 레벨의 노드는 일 수 있습니다. con 검색된 값을 유지하십시오.
리프 노드 레코드에는 키 값과 그 밖의 모든 데이터 레코드가 포함됩니다.
따라서 "실제"데이터는 리프 노드에만 포함되고 비 리프 노드는 키 값의 [사본을] 포함합니다. 매우 작은 비율의 데이터 (이 비율은 리프 노드에서 발견 된 평균 데이터 레코드 수에 따라 다름).
이 상단에서 Wikipedia article on B+ Trees 
비 리프 노드로부터 다음 이미지에 도시된다 (이 단순한 트리 유일한)는 두 개의 비 - 리프 노드 레코드 각각 포함 키값 (청색)의 복사본과 해당 노드 (회색 컬러)에 대한 포인터. 이 트리는 단지 두 레벨 만 가지므로 루트 노드의 "레코드"는 리프 노드를 가리 킵니다. 아래에 표시된 최상위 트리 위의 추가 레벨이 있다고 가정 할 수 있습니다 ("3-5 노드"라고 함). 그 경우 위의 노드는 (다른 유사한 레코드와 함께) "3-5"노드에 대한 포인터가있는 키 값 3을 가진 레코드를 포함합니다.
또한 리프 값이 아닌 노드에는 키 값 3과 5 만 포함됩니다 (즉, 이 아닌 키 값은 모두 비 리프 노드에서 재생 됨).
가 BTW이 예에서 잎 이외의 노드는 다음 노드의 마지막 레코드의 키를 포함합니다 (첫 기록이 대신 사용 된 경우에도 작동합니다, 검색 로직이 다음 구현 방식에 약간의 차이) .
리프 노드에는 키 값 (파란색으로 표시)과 해당 데이터 레코드 (회색으로 표시된 d1, d2 ...)가 있습니다. 각 리프 노드의 끝 부분에 표시된 적색 포인터는 다음 리프 노드, 즉 키 순서로 바로 다음 데이터 레코드를 포함하는 리프 노드를 가리킨다. 이 포인터는 다양한 범위의 데이터 레코드를 "스캔"하는데 유용합니다.
+0
b + tree의 모든 개념을 삭제했습니다 ...! 고마워. – rohit
1
모든 데이터가 나뭇잎에 있습니다.
0
BTrees 및 B + Trees에 약간의 혼란이 있습니다. B + 나무는 잎 노드의 데이터를 포인터로만 저장합니다. 즉, 데이터를 다른 위치에 저장해야합니다. BTrees는 모든 노드에 데이터를 저장할 수 있습니다. 장점과 단점이 각각 있습니다. 일부 사이트에서는 BTrees가 B + Tree와 정확히 동일 함을 나타냅니다.일반적으로 BTrees는 실제 데이터를 보유하는 것이 더 좋으며 B + Tree는 인덱스로 훨씬 효율적입니다.
B + 트리는 리프에 데이터 만 저장합니다. B- 트리는 내부 노드에 데이터를 저장할 수 있습니다. –