학생 ID 번호 및 기타 정보가 포함 된 정렬되지 않은 학생 정보 목록이 포함 된 파일이 있다고 가정 해 보겠습니다.B 트리의 보조 키
학생 ID 번호를 기반으로 학생 정보를 검색하는 프로그램을 만들고 싶습니다. 효율성을 높이기 위해 학생 ID를 B- 트리에 저장합니다.
그래서 학생 ID 번호를 입력하면 B- 트리를 검색하여 거기에 있는지 확인합니다. 또한 한 가지 더합니다. 학생 ID 번호를 찾으면 학생 정보가있는 파일의 위치도 반환합니다. 이것이 보조 키입니다. 프로그램은이 정보를 사용하여 나머지 학생 정보를 찾아 화면에 인쇄합니다.
이 작업을 수행 할 수 있습니까? 이것이 b-tree가 작동하는 방식입니까?
B 트리는 키에 대해 값을 저장하고 주어진 키와 관련 값을 로그 시간으로 찾을 수있게 해줍니다. 따라서 두 번째 것은 보조 키가 아니라 단지 가치입니다. 이 경우 파일에 대한 오프셋으로, 기본적으로 값에 대한 포인터가됩니다.
이것은 B- 트리를 사용하는 매우 합리적이며 매우 일반적인 방법입니다.
특히 B-trees와 관련이 없다 (BTW, B-tree이 무엇인지 이해하고 있습니까? 많은 사람들이 바이너리 트리를 혼동합니다). 파일 위치는 "보조 키"가 아닙니다. , 학생 ID가 매핑되는 값입니다.
그러나 관계형 데이터베이스는 내부적으로 사용자가 설명하는 것과 비슷한 방식으로 작동합니다. 즉, 데이터베이스 레코드는 여유 공간이있는 곳이라도 저장되며 인덱스는 인덱스 된 열의 값을 레코드의 위치에 매핑합니다.
B- 트리는 색인입니다 .B- 트리를 사용하면 색인을 사용하여 매우 효율적인 값을 찾을 수 있습니다. 색인 자체에는 노드와 리프가 있습니다. 각 노드에는 트리의 내용을 구성하는 데 사용됩니다. 노드 포인터는 다른 노드를 가리키거나 leafs. 그래서 노드는 일부 값과 일부 포인터를 보유하고 있습니다. 노드 포인터는 인덱스 파일로 전달되는 오프셋입니다. 리프에는 값과 포인터가 포함됩니다. 차이점은 리프의 포인터는 데이터 파일의 오프셋이며 진짜 파일.
그래서 실제 레코드가 저장된 파일 오프셋을 반환하기 위해 인덱스를 사용하는 값을 검색 할 때. ID = 1 인 레코드를 찾고있는 경우 예를 들어 오프셋 10240이면 1KB 블록이 있으면 블록 10을 읽도록 데이터 파일을 엽니 다.이 오프셋에서 예를 들어 Username과 같은 레코드의 모든 데이터에 액세스 할 수 있습니다!
또 다른 구현은 Leaf가 다른 파일을 가리키고 있지 않지만 두 번째 열을 보유하는 BTrees를 사용하는 것입니다. 예를 들어 ID를 사용하여 Username을 찾아야하는 경우 leafs가 다음 구조를 갖는 B Tree를 가질 수 있습니다. : 첫 번째 값은 id이고 두 번째 값은 사용자 이름이므로 인덱스에서 사용자 이름을 얻을 수 있습니다.
B + Tree를 사용할 수도 있습니다. B + 나무는 B 트리와 같이 구현되지만 목록에서 리프를 보유하고 있습니다.>와 같이 opperator에 인덱스를 사용할 수 있습니다. <.
B- 트리와 이진 트리의 차이점을 알고 있습니다. B- 트리는 각 노드에서 둘 이상의 값을 가질 수 있습니다. – neuromancer
@Phenom : 더 중요한 차이점은 B-Tree 노드는 2 개 이상의 자식 노드 (일반적으로 더 많은 노드)를 가질 수 있다는 것입니다. –