아래 첨부 된 스크린 샷에는 R 트리가 있습니다. 루트에 R1과 R2가 있습니다. R1의 왼쪽은 r3, r3, r5이다. 왜 그런가요? 나는 루트 엘리먼트의 왼쪽에있는 엘리먼트가보다 작아야한다고 생각했다. 루트의 루트 요소가 R6 인 경우 R3, R4, R5를 왼쪽에 넣는 것이 좋습니다. 지금까지 내가 아는 한 B +와 B- 나무가 그 규칙을 따른다.R 트리가 순서가 매겨지지 않은 이유는 무엇입니까? 그러나 B- 트리의 규칙을 따르는 것으로 알려져 있습니다.
또한 리프 노드에서 R12와 그 이후에 빈 공간이있는 이유는 무엇입니까? 나는 혼란스러워.
B 트리와 R-트리의 기반이되는 완전히 다른 개념. 유사한 이름과 높은 n - (따라서 랜덤 액세스 시간이 나쁜 디스크에 저장할 수 있도록) 공통점이 거의 없습니다.
B 트리는 자연스럽게 정렬 된 단일 차원 값을 저장합니다. R-tree는 자연스럽게 정렬 할 수없는 다차원 값을 저장합니다. (어떻게 x/y 좌표의 쌍을 주문 하시겠습니까?).
B 트리는 요소 자체를 저장하고 R 트리는 인위적으로 구성된 경계 상자의 좌표를 저장합니다. 위 이미지의 R i은 임의의 레이블 일뿐입니다. 원하는 이름으로 바꿀 수 있습니다.
B- 트리 및 R- 트리의 연결은 절대적으로 다른 관계를 의미합니다.
일부 B 트리 노드 기억 N 값은, 그때는 (의미) 인접한 값 사이의 위치 N +1 포인터가있는 경우. 예를 들어, 일부 포인터가 값 25와 70 사이에 있으면 26에서 69까지 요소를 저장할 수있는 하위 트리가 생깁니다. 따라서 B 트리의 연결은 중간에 을 의미합니다 관계. N 경계 박스 일부 R 트리 노드 좌표를 저장하는 경우
후 또한 낮은 수준으로 N 포인터마다 하나씩 바운딩 박스를 갖는다. 일부 포인터가 R i에 속하면 R i에 관련된 모든 내부 경계 상자를 포함하는 하위 트리로 연결됩니다. 이것은 일종의 "포함"관계입니다.
첫 번째 질문에 대답하십시오. R1은 R3, R4 또는 R5보다 작지 않습니다. 이들은 각각의 직사각형의 레이블 일뿐입니다. 대신, R3, R4 및 R5는 R1의 일부입니다.
빈 공간이있는 이유는 트리 구성에 사용되는 알고리즘에 따라 다릅니다. 서로 다른 알고리즘과 삽입/삭제 순서가 다르면 동일한 요소 집합을 포함하는 서로 다른 트리가 생성 될 수 있습니다. (B- 트리도 마찬가지입니다.)
그래서 r3, r4, r5도 왼쪽에 배치 할 수 있습니까? 의무가 아닌 ? – coder85
Gudok, R 트리에서 삽입 및 삭제가 어떻게 작동합니까? 온라인에서 본 설명은 너무 모호합니다. 그들은 그것을 자세히 설명하지 않습니다. – coder85
예. Ri가 Rj보다 크다고 말할 수는 없습니다 - 사각형에 정의 된 관계는 없습니다. 그러나 Ri가 Rj에 포함되어 있다고 말할 수 있습니다. 이것이 R3, R4, R5가 R1을 루트로하는 하위 트리에있는 이유입니다. 각 노드 내부의 값은 정렬 된 목록이 아닌 * set *으로 생각하십시오 (B 트리에서와 같이). R3, R4, R5를 R5, R3, R4로 쉽게 다시 구성 할 수 있습니다. 실제적인 impl은 물론 검색을 가속화하기 위해 노드 내부에 직사각형을 정렬합니다 (전형적인 노드는 수천 개의 직사각형을 포함 할 수 있습니다 - 위의 그림처럼 3 개뿐입니다). – gudok
1 차원 데이터 만 주문됩니다.
의 아이디어는 R-나무의 및 분할를 B 트리와 유사하다 균형; R-tree는 비슷하게 최소 페이지 채우기 등을 보장합니다. 페이지의 개념 역시 비슷합니다.
그러나 B- 트리는 선형 노드 순서를 사용하지만 R- 트리는 다차원 데이터가 정렬되지 않으므로 선형 순서가 아닌 경계 볼륨 계층 구조를 사용합니다. R- 트리에는 "왼쪽"또는 "오른쪽"이 없습니다.
누군가 도움을 줄 수 있습니까? – coder85