그래서 내 데이터 구조 클래스에 대한 프로젝트가 있고 아주 간단한 정보 데이터베이스를 구현해야합니다. 레코드는 파일에 저장해야하며 프로그램을 열 때 파일에서 읽고 BTree에 넣어야합니다. 내 문제는 우리가 아직 BTrees에 대해 이야기하지 않았으며 교과서의 강의가 너무 명확하지 않다는 것입니다 (코드, 설명 및 몇 가지 예가 없음).BTree 구현 - 먼저 트리 순서를 알아야합니까?
제 질문은 : 먼저 명령을 모른 채 BTree를 만들 수 있습니까? 또는 주문에 대해 매우 높은 숫자를 설정해야 레코드를 많이 맞출 수있을 것이라고 확신 할 수 있습니까? 어떤 제안?
확실히 할 수 있습니다 - BTrees는 입력을 정렬하도록 설계되었습니다. 필요한 것은 두 개의 개체를 비교할 수있는 능력뿐 아니라 어느 것이 더 큰지 또는 나중에 결정해야 하는지를 결정할 수있는 능력입니다. 당신이 그들에게 더 많은 레벨을 성장, 더 많은 항목을 추가로 BTrees 동적으로 성장. 나는 당신의 교수가 BTrees를 잘 다루기를 희망합니다. 매력적인 구조이기 때문에 :-).
과제의 일부로 BTree를 구현해야한다면 TA로 가서 자세히 설명해야합니다. 일반적인 아이디어는 각 노드가 정렬 된 값 또는 값의 범위에 따라 다른 노드를 가리키는 값. 이 트리에 노드를 추가 할 때마다 노드가 있어야하는 위치로 이동하고 가능한 경우 노드를 추가하십시오. 그렇지 않은 경우 트리가 가능해질 때까지 트리를 재구성 한 다음 노드를 추가하십시오.
악마의 세부 사항에,이 경우에는 세부 사항은 약간의 시간과 좋은 설명, 완전히 grok하는 데 걸릴 것입니다. BTrees가 궁극적으로 얼마나 크게 될 것인지, 요소가 어떤 범위를 커버 할 것인지 또는 다른 것을 미리 알 필요가 없기 때문에 사람들이 복잡성의 원인이되는 두통을 두드러지게하는 이유가 있습니다. 보너스로 디스크의 모든 요소를 메모리에 저장할 수없는 디스크에 사용하기에 매우 적합합니다.
자신 만의 BTree를 구현하는 경우 다른 주문을 지원할 수 있는지 확인해야합니다. 특히 사용하려는 주문이 매체에 따라 다를 수 있습니다. BTree의 목적은 랜덤 액세스를 수행하는 데 걸리는 시간을 최소화하는 것입니다. 따라서 메모리 내 BTree (그렇게 사용한다면)는 단일 노드를 캐시 라인에 넣고 싶을 것입니다. 디스크에 BTree를 저장하려면 (이 경우에 수행 할 것입니다) 노드가 디스크 섹터에 적합하도록해야합니다.
그래, 어떻게 할 수 있습니까? 내 말은, 최대 주문이 무엇인지 모르는 경우 어떻게 BTree를 구축해야합니까? 항목이 제 자리에 있는지 또는 제 위치에 있는지 여부를 지속적으로 확인해야합니까? – Mackiavelli
가능한 경우 TA 세션을 예약하십시오. 교과서는 이런 종류의 것들을 설명하는데있어서 끔찍합니다. 물론 끔찍한. 당신은 어떤 언어를 가장 좋아합니까? –
코스는 C++이기 때문에 C++ btree가 도움이 될 것입니다. – Mackiavelli