前回は主に線形データ構造を紹介しましたが、今回の233ソースでは、どこにでもある非線形のデータ構造の1つであるツリー構造の特徴と応用について紹介します。
ツリー構造は、参照：ツリーデータ構造のようなデータ要素間の関係。絵を見て話してください：
- 各ノードは、子ノードの有限の数だけを持っているか、子ノードを持っていません；
- 親ノードを持たないノードをルート・ノードと呼びます；
- 親ノードを持たないノードはルート・ノードと呼ばれます；
- ルート・ノード以外の各子ノードは、複数の不連続な部分木に分割できます；
- ツリー内部にループはありません
ウィキペディアには、コンピュータサイエンスにおける木構造の種類が記載されています。
今回は紙面の都合上、LSMツリー以外の内容を中心に紹介します。
###多項木は一種の 継承 関係を具現化したものであり、ノードは親子関係によって互いに関連しています。多項木は 、親ノードが複数の子を持つことができる木 です。つまり、父親は複数の息子を持つことができ、息子は1人の父親しか持つことができません。
また、ノードの各ブランチは、選択肢を表し、意思決定を行うために使用することができます。
アプリケーションのシナリオ：1 Linuxのファイルシステム2組織の関係は、会社の組織構造、役割のアクセス許可システムなどのように。3.XML/HTMLデータ。4.クラスの継承関係 5.ゲームのモンスターが使用するスキルの選択などの意思決定、機械学習...### 分岐ツリー分岐ツリーとは、1つのノードに最大2つの枝があるツリー構造のことです。
コンピュータのアプリケーションでは「白か黒か」のシナリオが多いので、この構造を利用して、左の枝か右の枝のどちらかを選択して、何らかの決定を下すことが可能です。また、各ノードの参加者が最大2人であることを利用することも可能です。シナリオ： 1. コンパイラの構文木構築 2.2.式の評価と判定：非リーフノードは演算子、リーフノードは値。3.論理評価、例えば or .4.ホフマンコーディング 5.IPv4ルーティングテーブルの格納...
日々の開発では、データの追加、削除、チェックが必要になることが多く、各ステップの時空間効率がアプリケーションの最終的なパフォーマンスを決定します。
時間の複雑 さは、操作するデータ要素を素早く見つける能力に反映され、コアは インデックスの良し悪しにあります；
空間の複雑 さは、アクセス速度を向上させるために、コンピュータのメディアキャッシュの様々な層の性能を活用するかどうか、より少ないメモリ空間を占有する能力に反映されます。
以下のツリー構造の考察では、データの追加、削除、検索のパフォーマンスを、 インデックスの作成、メモリ空間の占有、操作媒体の 側面から考えていただければと思います。
### バイナリルックアップツリーバイナリルックアップツリーは、まずバイナリツリーであると同時に、ノードの左の子は自分より小さく、ノードの右の子は自分より大きいというある程度の順序性を満たします。
アプリケーション・シナリオ: バイナリ探索木の順序付けられた性質は、それが広く使用できる理由です。しかし、効率的に分岐する能力は、木の高い合理性に反映されています。以下のような赤黒木/ヒープ構造が広く使われています。
###二分木の欠点は、ノードの順序だけを制限することですが、順序付き木には良い方法と悪い方法があります。悪い」順序木は「順序リスト」に引っ張られる可能性があります。ですから、木がある条件によってバランスが取れていることを確認する必要があります。
ツリーのバランスは、最高のサブツリーと最短のサブツリーの全体のツリーを指しますあまり違いは、ツリー全体の高さが比較的低いように、対応する増加、削除、変更、操作の効率が高く、より安定しているチェックします。
- ノードは赤または黒。
- ルートは黒です。
- すべての葉は黒です。
- 各赤ノードは、2つの黒子を持っている必要があります。
- 任意のノードからその葉の各々へのすべての単純なパスは、同じ数の黒いノードを含みます。
これらの制約により、赤黒木の重要な特性である「根から葉までの最長パスは最短パスの2倍以下」が保証されます。その結果、木全体の高さはより安定し、対応する追加、削除、変更、ルックアップ操作は、通常の2進ルックアップ木とは異なり、より効率的で安定します。
また、他のバランス木と比較すると：高バランス木AVL木など、赤黒木は、追加、削除、および変更でより効率的であり、同時に、検索のパフォーマンスが低下していない多くのも、より安定しています。したがって、より広く産業レベルで使用されています。
アプリケーションのシナリオ：ソートに適した、シーンを検索します。1.JavaのHashMap/TreeMapなどのコンテナの基本的な構成。 2.Linuxカーネルの完全に公平なスケジューラ。 3.Linuxのエポール機構の実装...
### ヒープ ヒープは2つの性質を満たす特殊なデータ構造です：
- ヒープは完全なバイナリ・ツリーです；
- ヒープ内の各ノードのソート値は、その左右の子ノードのソート値以上でなければなりません。
ここで完全二分木について説明します。これは、最後の層を除くすべての層のノード数が完全であり、最後の層のノードが左から順番に並んでいることを意味します。
これにより、配列に格納することが可能になります。
iの位置のルートノード= 0と仮定すると：配列添え字iの親ノードの場合は、配列添え字2 * i + 1の左の子ノード、配列添え字2 * i + 2の右の子ノード。
ポイント2については、各ノードの値がサブツリーの各ノードの値以上である場合、ヒープは "大きなトップヒープ "と呼ばれています。その逆は「スモール・トップ・ヒープ」と呼ばれます。
ヒープとは、最も小さい要素か最も大きい要素のいずれかがヒープの最上位にある、相対的な順序構造です。そして、配列の使用と、追加、削除、変更、チェックという独自の特性により、時間の複雑さが低い。
アプリケーションシナリオ： 1.ヒープソート 2.TopK、中央値、 3.複数の順序付けられた小さなファイルやコレクションのマージ 4.
###トライ・ツリートライ・ツリーは 、接頭辞ツリーや辞書ツリーとしても知られ、文字列マッチングに特化 したデータ構造で、文字列のコレクションから文字列を素早く見つける問題を解決するた めに使用されます。
その特徴は
- ルート・ノードには文字が含まれず、ルート・ノード以外のすべての子ノードに文字が含まれること。
- ルート・ノードからあるノードまで、パス上で渡された文字をつなげて、そのノードの対応する文字列とします。
- 各文字列の共通接頭辞は文字ノードとして保持されます。
トライツリーの本質は、文字列間の共通接頭辞を使って、重複する接頭辞をマージすることです。したがって、文字列を探すときには、トライツリー内の各文字をマッチさせればよく、比較の回数は文字列の長さに関係するだけです。
しかし、トライツリーの欠点は、トライツリーを構築するために多くのメモリ領域を必要とすることです。なぜなら、親と子の文字ノードはポインタによって関連付けられているからです。これらのポインタを格納するために配列を使用する場合、子ノードの配列はそれぞれの可能性を網羅する必要があることを意味します。たとえば、子ノードの文字が a ～ z の場合、これらの可能性のある子ノードを格納するために長さ 26 の配列を割り当てる必要があります。
メモリ割り当ての改善は
1.子ノードのポインタは、順序付き配列、ジャンプ・テーブル、ハッシュ・テーブル、赤黒ツリーに置き換えられて格納されます。2.サブノードがマージされます。例えば、元のhelloは次のように格納されます： h->e->l->l->o ,今は次のように格納できます： h->e->llo
トライツリーは、結局のところ、スペースの無駄なので、それは文字列検索にあり、次の場合に適しています：1.文字セットが大きすぎることはできません2.公開接頭辞の文字列より多くのシーン。
アプリケーションのシナリオ：1.キーワードのマッチング、ヒント、エラー訂正。2.最長の公開接頭辞のマッチング。3.zshなどのコマンドの自動補完。 4.URLの閲覧履歴。5.携帯電話番号のディレクトリクエリ...
Bツリー、B+ツリー、LSMツリーは、データベースで頻繁に使用されるデータ構造です。データベースの追加、削除、クエリを効率的に行うために考慮すべき主な要因は、ディスクへのIOアクセス数です。
IOアクセス数を減らすには？
インデックスは前述しましたが、ディスクからデータを取得するために、一度IOは、通常はブロック単位であり、容易ではありません。データの数千万の場合は、インデックス構造の唯一の1つの層は、インデックス化されたデータの量も膨大です。
インデックスの量を減らすには？
世界中を回って人を探す場合、国／県／市／区／通り／近所の順に探すとします。同様に、データ量が増えるにつれて、レイヤーごとに 複数レベルのインデックスを 構築する必要があります。インデックスが高ければ高いほど、各ブロックで表現されるデータの範囲は大きくなります。
正しい」マルチレベル・インデックスを構築するには？
適切とは、格納するデータ量が大きく、ツリーの高さが小さいことです。赤黒木と同様に、木の高 さには制約が あります。これが以下のデータ構造の制約の理由です。
###次数mのB木は次のような特徴があります：
1.ルート・ノードが少なくとも2つの子を持つこと。2. 各中間ノードはk-1個の要素とk個の子を含み、ここでm/2 <= k <= m 3. 各葉ノードはk-1個の要素を含み、ここでm/2 <= k <= m 4. すべての葉ノードは同じレベルにあります。5. 各ノード内の要素は小さいものから大きいものへと並べられ、ノード間のk-1個の要素は、k個の子に含まれる要素の値域分割と正確に一致します。
3次のB-tree挿入を以下に示します：
アプリケーションシナリオ: MongoDB
###B+ツリー
次数 m の B+ ツリーには次のような特徴があります：
1.中間ノードに含まれるk個の要素を持つk個のサブツリーがあり、各要素はデータを保持せず、インデックス付けにのみ使用され、すべてのデータはリーフノードに保持されます。2.すべてのリーフノードには、すべての要素に関する情報と、これらの要素を含むレコードへのポインタが含まれ、リーフノード自体はキーワードのサイズに従って小さいものから大きいものへと順にリンクされています。3.すべての中間ノード要素は子ノードに存在し、子ノード要素の中で最も大きい。
この問題は理解できませんが、これらの制約が、B +ツリー・データを「短くて太い」良いものにするためのものであることだけは知っておいてください。
アプリケーションのシナリオ 1.Mysql InnoDBストレージエンジン。
Bツリー対B+
B-treeとB+-treeの大きな違いは、1.B-treeの非リーフノードはインデックスとデータであり、B+-treeの非リーフノードはインデックスのみで、データはすべてリーフノードに格納されます。2.B+ツリーのリーフノードのデータは、チェーンテーブルでリンクされます。これにより
B+木とB-木の比較：1.データの連続性：
- B+ツリーのリーフノードのページに保存されたデータは連続的で、ノードのデータが必要なときに、B+ツリーはキャッシュヒット率を高めることができます。
2.リーフノード間の接続性：
- 範囲スキャンまたは全文スキャンとして、B+木はノードの各レベルでのみスキャンを行うことができますが、B+木は線形シーケンシャルスキャンを行うリーフノードに依存することができます。 B+木はまた、キャッシュのヒット率を向上させることができます。
B-treeとB+-treeの比較：単一のデータクエリを実行する場合、B-treeのノードは平均してルートノードに近く、平均クエリ効率はB+-treeよりも高速です。
まとめると、B+木とB木の比較では、前者の方が範囲クエリに適しており、後者の方が単一データクエリに適しています。
Mongoは非リレーショナルデータベースです。その主な使用シナリオは：単一の読み取りと書き込みレコードのパフォーマンスの追求。
Mysqlはリレーショナルデータベース、共通のインデックスキーとデータ間の関係は、ソリューションを結合します。その使用シナリオ：だけでなく、単一のデータのクエリの数が多いの存在だけでなく、範囲のクエリの数が多い。
だから、上記の質問は、単純なそれを引っ張ることができます。
LSMのツリー：次の記事233ソースは、近年ではしばしば表示されるデータベースの役割を紹介する準備が整いました。 この記事が得たり、次を楽しみにしていると思う233ソースをサポートするように、に注意を払ってください〜！
[1].ウィキペディア
[2]
[3]
[4]
[5]
