私はClojureのデータベースをおもちゃに取り組んでいて、B +ツリーを実装したいと思っていました。私がそれについて考え始めると、Clojureの他のノードへのポインタ/参照のようなものを持つ方法がないかもしれないことに気付きました。あなたが必要とするのはNodeの子を格納するだけなので、BSTや他の多くのTree構造のようなものには関係ありません。しかし、ノードの兄弟を参照する必要があるB +ツリーのようなものではどうしますか？Clojureでポインタ/参照を必要とするデータ構造を記述していますか？
解決策を探しているとき、私はClojureで他の方法があるので、ClojureでDoublyリンクリストを実装しない方法についてGoogleグループの投稿に出くわしました。
私はB +ツリーのために何をしますか？
クロージャーでオブジェクトを参照するのは難しいことではありません。一般的に、これらの参照は不変です。単一リンクリストと違って、どこかで突然変異を作成せずにその部分を変更することはできないので、二重連結リストを不可能にする不変性です。これを確認するには
、私は、単独でリンクリストを持っている
a -> b -> c
と私はそれの頭を変更したいと考えます。私はリストの全体を変更して、そうすることができます。ヘッド値の新しい値を作成して、テールを再利用して新しいリストを作成します。
a'-> b -> c
ただし、重複したリストは不可能です。したがって、クロージャーやその他の関数型言語では、このような状況でzipperを使用することがあります。
Clojureで実際に変更可能な参照が必要だとしたらどうでしょうか？さて、何が必要同時実行のセマンティクスに応じて、Clojureのはvars、refs、など
を持っている。また、deftypeで、あなたは可変フィールドを持つオブジェクトを作成することができ、これらの変更可能なフィールドは、他のものへの参照を保持することができます。この同じ目的のために、クロージャで生のJava配列を使用することもできます。
データベースはインメモリデータベースまたはディスクバックアップデータベースになりますか？ディスク上にある場合は、pointer swizzlingの問題は、変更可能な参照を持つよりも扱いにくいと思います。
機能的なデータ構造の問題に戻って、純粋に機能的なセマンティクスを持つBツリーを作成することは可能です。ここでの最初の手がかりは、それが木であり、木は機能的なデータ構造のパンとバターです。第2に、append-onlyの方法で動作するデータベース、例えばcouchDBがあることに注意してください。これは、ある意味で、データベースが独自のログであるという利点があります。このアプローチのコストと利点のアイデアをもっと得るには、watch Slava Akhmechet's presentationが望ましいかもしれません。彼の会社、RethinkDBは、最終的には、IIRCのようなハイブリッドアプローチを採用しました。
あなたの答えをありがとう。 DBはおそらく今のところ記憶に残っていますが、その過程でClojureについて学ぶつもりであるようです。 – TriArc
ClojureのChouser's finger treesを参照して、機能的スタイルを使用して二重リンクされたリストの機能を実装する方法を確認してください。
また、B +が機能的言語のデータ構造の良い選択であると信じている理由を尋ねてください。
Chris Okazakiの書籍「Purely Functional Data Structures」を参考にしてください。"
私は伝統的なB +ツリーに代わるものを探してみます 理由はB +ツリーを使用したかったのは、最終的にディスクにデータを保存したいからB +ツリーがこのようなシナリオ、特にディスクアクセスの少ない範囲照会に最適です。 – TriArc
私はこの問題を完全には理解していませんが、好奇心から外れています：リンクリストはなぜ他の方法で問題を解決できなかったのですか？ – Belun
リンクリストを実装しようとしていませんでした。私がB +ツリーを実装している、つまりノードへの参照を扱っている問題は、リンクされたリストを扱うときに遭遇するものと同じです。 – TriArc