skillup

技術ブログ

Database

データ構造の基礎知識 後編 木構造

投稿日:2016年7月27日 更新日:

データベースの学習をしていたときの復習です。

データ構造の基礎知識 前編 メモリとポインタ、配列と連結リスト

データ構造の基礎知識 中編 ハッシュ

今回はもう少し複雑な「木構造」について考えてみます。

木構造とは?

下記のような特徴があります。

  • 要素同士に親子関係がある
  • 親は複数の子を持てる
  • 子から親へ循環して親子関係になることはない

2分木構造

  • 親は0~2個の子供を持つ
  • 大小関係は左の数<親<右の数となる

下記リンクが一番イメージしやすい。

メリット

  • キーが常にソート済み
  • 各要素へのアクセスがO(logn)
  • 要素を追加してもハッシュのようなrehashは不要
  • ハッシュと違い、無駄になるメモリがないためメモリ効率が良い

デメリット

  • 偏った木構造(枝が一本のみ)の場合,O(n)になる

そこでこのデメリットを補うために、B木という構造が使われます。

B木

  • 各ノード内では値はソート済みの状態で保存されている
  • 各値の左側から生えている枝からたどれる値はその値よりも小さい値
  • 各値の右側から生えている枝からたどれる値はその値よりも大きい値

 

-Database
-

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

SQL サブクエリ

前回の問題をサブクエリを使って解きます。前年度の売上を出すのが一番難しいので、それを出す方法です。MySQLだとそもそも分析関数が存在しないので・・ [crayon-62bed6a084bac2880 …

no image

第二、第三の正規化&ER図&Check制約

前回第一正規化を話したので、第二、第三に進んでいきます。 Contents1 第二正規化とは?2 第三正規化とは?3 正規化のメリット4 ER図5 本日のSQLネタ Check制約 第二正規化とは? …

no image

SQLで数列を扱う

今回はSQLで数列を扱ってみましょう。 例えば下記のような0から9までの数字が書かれている数列があったとして、 これにより連番を作成してみましょう。 digit ——- 0 1 …

no image

アンチパターン トランザクションスコープ+大量データのリアルタイム集計+接続が詰まる

本日は主にインフラの設計的なことに関して。 Contents1 トランザクションスコープの設定1.1 デメリット1.2 対策2 大量データのリアルタイム集計2.1 デメリット2.2 対策3 詰まると接 …

no image

インデックスについて(SQLServer)

DBのインデックスについて、今までぼんやりと検索条件の効率化についてはしっていたのですが、もう少し掘り下げて理解する必要があるなと思い、メモります。 SQLServerのインデックスについてすごくまと …

アーカイブ