treee
Update with Windows10 and MacOS executables
ハッシュされたIDによって識別され、不変のファイルに保存されているデータの高速インデックスエンジン
これは、Treee™インデックスエンジンのGO実装です。これは、GOプロジェクトのモジュールとして使用するライブラリと、HTTPを介してマイクロサービスとして実行する実行可能ファイルの両方です。
課題は、データがサブチェーンで互いに接続される可能性のあるアイテムのリンクされたリスト、ハッシュ値（SHA-256文字列表現など）のみで作られ、すべてが不変のファイルに保存されている識別子を介してインデックス付けされた場合に使用する強力で安全な検索エンジンをセットアップすることでした。
その最良のアプリケーションは、アイテムがスマートコントラクトを埋め込むトランザクションであるブロックチェーンファイルと、その後のスマートコントラクトの使用および/または変更をアイテムの各サブチェーンです。そのため、Treee™インデックスは現在、Rooot™ブロックチェーンで使用されています。
ここでは、ライティングと読み取りに非常に強力なハッシュ値である識別子に基づいてシステムをインデックス作成するためのアルゴリズムを定義します。
Treee™インデックスは、非環式グラフ（ツリー）として構築されています。各ノードには、ノードアドレス（息子）またはリーフのセットのいずれかが含まれています。これは、1つ以上のリンクされたアイテムを取得するのに役立つ情報に対応する葉です。
ノードの息子の数は決定論的であり、ツリーの深さに依存します。深さ1のノードの息子の数、深さ2のノードの息子の数、...、深さの息子の数を示します。
目標は、幅が深さを減らし、パフォーマンスを最適化するために適応するバランスのとれたツリーを作成することです。この場合、アイテムの一意の識別子の数値をインデックスを付けようとしています。
インデックスのコースを説明しましょう。
バイナリツリーの場合、ツリー内の位置を示すバイナリ形式（たとえば、 100 ）で数字を書きます。
ステップでは、ビットが0の場合は子供に渡されます。そうしないと、ビットが1場合は子供に渡されます。ノードが葉であるときに停止します。
ツリーの場合、一連の数字でこの数値を表現し、同じ方法でツリーを横断します。深さの段階で、代表者が0 1場合は子供に渡ります。ノードが葉であるときに停止します。
数の表現を構築するために、素数の弾性モジュロを連続して採取します。中国の遺物の定理によると、各数値には、これらのモジュロの継続として書くことができるユニークな代表者がいます。実際、数字は次の形式で書くことができます。
アイテムの識別子（その数）の値は示され、変調数が表示されます。モジュロスは、固定サイズの整数に対して計算されます。乗算は分割よりも高速であるため（モジュロの計算に必要）、フローティングを使用して乗算を使用できます。
数字のランダムな性質（または、アイテムの識別子が暗号化ハッシュテクノロジーによって生成されるため、擬似ランダム）を考えると、ツリーはバランスが取れています。悪意のある方法で木をバランスを崩すためには、モジュロが特定の軌道に従うハッシュを生成できるようにする必要があります。ただし、このような操作の難しさは、（深さがどこにあるのかの順序の）指数関数的に増加します。リマインダーとして、最初の16の素数の製品は等しくなります。したがって、インデックスに合理的に大量のデータが含まれるとすぐに、悪意のある方法でツリーを不均衡にすることは、可能であればますます不可能になります。
葉には、アイテムに関する以下の情報リストが含まれています。
次のアイテムフィールドが空の葉は、サブチェーンの最後のアイテムです。
オリジンアイテムフィールドが現在のアイテムの識別子に等しい葉は、必然的にサブチェーンの起源です。そのため、特定の動作があります。その後、1つ以上のアイテムがある場合、サブチェーンの最後の項目は以前のアイテムとしてここで識別されます。したがって、葉の最後の3つのフィールドは、円形のリンクリストに対応しています。
インデックスに要素を追加するには：
インデックス内のアイテムを読み取り/検索するには：
インデックスを使用すると、最大3つの読み取りまたは3つの書き込みとインデックスの順序で実行されることがわかります。ここでは、インデックス内のアイテムの数があります。
詳細については、完全なホワイトペーパーをお気軽にお読みください。
$ go get github.com/cyrildever/treee import (
"github.com/cyrildever/treee/core/index"
"github.com/cyrildever/treee/core/index/branch"
"github.com/cyrildever/treee/core/model"
)
// Instantiate default index (could be any prime number up to the 1000th existing prime number,
// but should be much lower to better leverage the solution, and if 0 will use the default INIT_PRIME value)
treee , err := index . New ( index . INIT_PRIME )
if err != nil {
// Handle error
}
// Add to index
leaf := branch. Leaf {
ID : model . Hash ( "1234567890abcdef" ),
Position : 0 ,
Size : 100 ,
}
err = treee . Add ( leaf )
if err != nil {
// Handle error
}
// Search
if found , err := treee . Search ( leaf . ID ); err == nil {
// Do something with found Leaf
}パフォーマンスを向上させるには、検索リクエストをさまざまなゴルチンに配置する必要があります（たとえば、API/Handlers/Leaf.goファイルのGetLeaf()実装を参照してください）。
デバッグまたはストレージの目的では、 TreeeインデックスのPrintAll()メソッドを使用して、記録されたすべての葉をライターに印刷することをお勧めします（印刷されたJSONを美化するための議論として、または生の文字列のtrueとしてそれを渡しfalse ）。
// To print to Stdout
fmt . Println ( treee . PrintAll ( true ))インデックスの永続性は、挿入時に行われた自動保存と、起動時にNew()を使用したtreeeインスタンス化の代わりにLoad()関数の使用を使用することで達成されます。
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"対応する環境変数またはコマンドラインのフラグを使用して、またはプログラムでさえも無効にすることができます。
treee . UsePersistence ( false ) // If you're positive you don't want it実行可能ファイルを構築して、Treee™インデックスエンジンのインスタンスを開始できます。
$ git clone https://github.com/cyrildever/treee.git && cd treee && go build
$ ./treee -t.port 7001 -t.host localhost -t.init 101 Usage of ./treee:
-t.file string
File path to an existing index
-t.host string
Host address (default "0.0.0.0")
-t.init string
Initial prime number to use for the index (default "0")
-t.persist
Activate persistence (default true)
-t.port string
HTTP port number (default "7000")
設定されている場合、次の環境変数は、コマンドラインで渡された対応するデフォルト構成またはフラグをオーバーライドします。
HOST ：ホストアドレス。HTTP_PORT ：使用するHTTPポート番号。INDEX_PATH ：JSON形式のインデックスファイルへのパス。INIT_PRIME ：最初の素数（後者が勝つため、ファイルを使用しても効果はないことに注意してください）。USE_PERSISTENCE ： falseを設定して、インデックスをファイルに保存することの使用を無効にします。 次のエンドポイントは、 /apiグループの下で使用できます。
DELETE /leafこのエンドポイントは、渡されたアイテムをインデックスから削除します。
ids引数としてのIDSの配列が予想されます。
DELETE /api/leaf?ids=1235467890abcdef [ ... ] &ids=fedcba0987654321 [ ... ]
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Host: treee.io
Accept-Language: fr-FR
Accept-Encoding: gzip, deflate
Accept: application/jsonすべての渡されたアイテムが削除された場合は204ステータスコード、または削除されていない場合は、次のJSON IDの次のJSONリストとともに200ステータスコードを返します。
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafこのエンドポイントは、合格したIDに基づいてアイテムを検索します。
idsクエリ引数としてのIDSの配列とオプションのtakeLast Boolean（デフォルトにfalse ）が期待されます。 http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
次の形式を尊重するJSONオブジェクトとともにステータスコード200返します。
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
]アイテムが見つからなかった場合、空のボディを持つ404ステータスコードを返します。
GET /lineこのエンドポイントは、同じサブチェーン/ラインのすべてのIDを返します。
idクエリ引数としてのIDのIDが予想されます。 http://localhost:7000/api/line?id=1234567890abcdef[...]
次のJSONソート付きIDSの配列を使用して、 200ステータスコードを返します（インデックス0は原点です）：
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
]アイテムが見つからなかった場合、空のボディを持つ404ステータスコードを返します。
POST /leafこのエンドポイントは、インデックスにアイテムを追加します。
次のJSONオブジェクトが本体として期待されています。最初の3つのフィールドは必須です。
{
"id" : " <The item ID as a hash string representation> " ,
"position" : 0 ,
"size" : 100 ,
"previous" : " <An optional item ID of the previous item in the current subchain if any> "
}ステータスコードと次のオブジェクトをJSONとして返します。
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}ステータスコード（およびその意味）のリストは次のとおりです。
200 ：挿入されたアイテム。303 ：アイテムはすでに存在しています（ファイルが不変であると想定されるため、更新されていません）。400 ：間違ったパラメーター（不足しているアイテム、必須フィールドの欠落など）;404 ：以前のアイテムが見つかりませんでした。412 ：渡されたデータの何かがサーバーに失敗しました（JSON形式が正しくありません...）;500 ：サーバーでエラーが発生しました。平均して、基本的なマシンは1億人以上の新しいレコードを摂取し、1時間あたり約50億の検索クエリを処理できるはずです。
例として、Apple MacBook Pro 2.3 GHz Intel Core I9で16 GO DDR4 RAMが2400 MHzでクロックされているため、 101 initプライムとして使用するときに次のパフォーマンスを観察しました。
101れています。このモジュールは、MITライセンスの下で配布されます。
ライセンスファイルを参照してください。
