Java で B+-Tree の簡単な実装を作成したいのですが、助けが必要です。検索、挿入、削除などの機能をプログラムに実装したいと考えています。
私の質問:
また、推奨事項がある場合、または参考として使用できる簡単な実装を念頭に置いている場合は、教えてください。
ありがとう
B ツリー (または存在する小さなバリエーションのいずれか) の要点は、データをディスクに格納して、少数のディスク アクセスで読み取ることができるようにすることです。すべてをメモリに保持する場合は、バランスのとれた二分探索木 (おそらく赤黒木またはスプレイ木)、またはバニラ BST を使用する必要がありますが、どちらの質問もこの事実を考慮していないようです。
- ツリーを表すために使用するのに最適なデータ構造は何ですか? 私はツリーマップを考えていました。
TreeMapはメモリ内のデータ構造であるため、これがディスク上のツリーを表現するのにどのように役立つかは不明です。また、これはバイナリ サーチ ツリーを実装するため、TreeMap.
- B+-Tree では、データはすべてリーフ ノード (K,V) に保存され、すべてのレコードのデータの代わりに内部ノードに子ノード (K,P) へのポインターがあります。Javaでポインターを使用できないため、他のノードを指す方法について提案をお願いします。
B ツリーを表すために実際のポインターは必要なく、ファイル オフセットだけが必要です。これらのオフセット (実装の残りの部分がどのように構成されているかに応じて、ファイルの先頭からのバイト数またはブロック数) を表す方法を定義し、ファイル オフセットに関してすべてにアクセスする必要があります。実際、B+ ツリー内のノード間を指すために、標準の C スタイルのポインターを使用しないでください。そうした場合、それらのポインターは次回プログラムが開始されたときに無意味になるため、ディスク上のデータ構造の永続性の利点が失われます。
ファイルの内容にきれいにアクセスするには、メモリ マッピングをお勧めします。Java でメモリ マップト ファイル オブジェクトを作成するための便利な方法の 1 つは、FileChannel.mapです。このメソッドはMappedByteBufferを返します。これを使用して、特定のファイル オフセットでバイトのチャンクを読み取ることができます。