B + -Tree in Java

Question

Java에서 B + -Tree의 간단한 구현을 만들고 싶습니다. 도움이 필요합니다. 내 프로그램에서 검색, 삽입, 삭제 등의 기능을 구현하고 싶습니다.

내 질문 :

1. 트리를 표현하기 위해 사용하는 가장 좋은 데이터 구조는 무엇입니까? 나는 생각 TreeMap이었다.
2. B + -ree에서 데이터는 리프 노드 (K, V)에 저장되고 모든 레코드의 데이터 대신 내부 노드에 저장됩니다. 자식 노드 (K, P)에 대한 포인터가 있습니다. 나는 자바에서 포인터를 사용할 수 없기 때문에 다른 노드를 가리키는 방법에 대한 제안은 을 제안하고 싶다.

또한 권장 사항이 있거나 참조로 사용할 수있는 간단한 구현을 염두에두면 알려주세요.

감사

Answer 1

온전한 B - 트리 포인트 (또는 존재하는 작은 변화 중 어느 하나)가 디스크 액세스 소수로 판독 될 수 있도록 디스크에 데이터를 저장하는 것이다. 모든 것을 메모리에 보관하려면 밸런스 이진 검색 트리 (빨간색 또는 검은 색 트리 또는 스플래시 트리) 또는 바닐라 BST를 사용해야합니다. 그러나 질문을해도이 사실을 고려하지 않은 것입니다.

1. 트리를 나타내는 데 사용할 수있는 최상의 데이터 구조는 무엇입니까? 나는 TreeMap을 생각하고 있었다. 그것은이 온 디스크 트리를 표현하는 데 도움이 방식이 불분명 있도록

TreeMap는 메모리 내 데이터 구조입니다. 또한이 방법은 이진 검색 트리를 구현하므로 TreeMap을 사용하면 B- 트리를 실제로 구현하지 않습니다.

<올 시작할 = "2">은 B에서

+ 데이터 리프 노드에 olny 저장된다 - 트리 (K, V) 대신 모든 기록 데이터의 내부 노드들에 대한 포인터가 자식 노드 (K, P). 자바에서 포인터를 사용할 수 없기 때문에 다른 노드를 가리키는 방법에 대한 제안을 원합니다.

파일 오프셋뿐 아니라 실제 포인터가 B- 트리를 나타내는 데 필요하지 않습니다. 이러한 오프셋을 표현하는 방법 (나머지 구현 방식이 어떻게 구성되어 있는가에 따라 파일의 시작 부분부터 바이트 또는 블록 수)을 정의하고 파일 오프셋과 관련된 모든 항목에 액세스해야합니다. 실제로 이 아니라 표준 C 스타일 포인터를 사용하여 B + 트리의 노드를 가리 킵니다. 그렇게했다면 다음 번에 프로그램을 시작할 때 그 포인터는 의미가 없으므로 디스크상의 데이터 구조의 지속성 이점을 잃게됩니다.

파일 내용에 깨끗하게 액세스하려면 memory mapping을 권장합니다. Java에서 메모리 매핑 된 파일 객체를 만드는 유용한 방법 중 하나는 FileChannel.map입니다. 이 메서드는 MappedByteBuffer을 반환합니다.이 메서드를 사용하면 특정 파일 오프셋에서 바이트 청크를 읽을 수 있습니다.