大規模ウェブサイトのアルゴリズムとアーキテクチャについての簡単な説明（パート 2）

順序

前回の記事「大規模 Web サイトのアルゴリズムとアーキテクチャに関する簡単な説明 (パート 1)」に続いて、このトピックを続けましょう。

上記で多くの人が話題に関係ないと言っています。これは情報の一部に過ぎないので、話題に関係ないと感じるかもしれません。主な理由は、話題が大きすぎて内容が多すぎるためです。部分的にしか書き出せません。ご容赦ください。

上司は上のことしか話しませんでしたが、真ん中や下もありますよ！

重点は基本的な部分、つまりアルゴリズムの部分にあります。これには、今日のアーキテクチャの製品で使用されるアルゴリズムが含まれており、製品の本質をある程度理解することができます。関連する建築製品について実際に話す前に、スプレーツリーに関する記事から始める必要があります。

彼はまだ始めてもいないのに！勉強するには少し時間がかかりそうです。まずはアルゴリズムを理解しましょう！

バイナリツリー

上記の 2 つの構造 (配列とリンク リスト) には、それぞれ欠点があります。

1》配列は更新時に多くのリソースを消費し、後続の要素を1つずつ移動する必要があります。

2》リンクリストを照会する場合は、先頭から1つずつ比較して、照会する内容を選択する必要があります。

要約すると、クエリと更新がより高速な構造が必要なので、バイナリ ツリーを使用します。

特徴：

各ノードには最大 2 つのサブツリーがあります。

80を見つける

実際のコードを見てみましょう:

[[94946]]実行して見てみましょう

挿入82

コードの練習を見てみましょう (注: 元のコードにメソッド insert_bit_tree が追加されています)。

[[94946]]実行して見てみましょう

#p#

バイナリツリーの問題点

非常に極端なケースで特定のデータを検索すると、上図に示すような状況が発生することは容易にわかります。データが数千万個あったら何が起こるかわかりますか?

上記の理由から、AVL ツリーとも呼ばれるバランスのとれたバイナリ ツリーを考えました。

バランス二分木: AVL 木 (1962)

実際のコードを見てみましょう。

主にこのコードを理解する

[[94946]]この関数をグラフに描きます。

オリジナルリンク: http://www.cnblogs.com/baochuan/archive/2012/10/08/2713700.html