隣接リストモデルを閉包テーブルモデルに変更したった

これは[Hubble Advent Calendar 2023](https://qiita.com/advent-calendar/2023/hubble)の13日目の記事です！

# 謝辞
私は技術記事の投稿が初めてになります。
実を言うと記事なんて一生書かないと思っていました。それは単純な話で日本に住んで30年になるのですが、今だに日本語力が低いためです。
何かを書こうとしても文章を考えすぎたり、正確性を求めて時間がかかるので避けていました。
そんな中HubbleでAdvent Calendarに参加するにあたり、記事を書くエンジニアを募ることになりました。
そこでCTOの@katsuya0515さんに「これって参加しなきゃダメですか？」と問うと「どちらでもいいけど、せっかくならやってみましょう！」とのことだったので、軽い気持ちで参加して記事を書くことになりました。
こんな機会をくれたHubbleの皆さんに3000回愛していると伝えたいです。chu

# はじめに
おはこんばんにちは！
私は株式会社Hubbleにて業務委託でバックエンドをしているnohataと申します！
この記事の対象者は**隣接リストモデル**を**閉包テーブルモデル**にしたいorそんな話読んでみたいと言う方になります。
今回の件で必要なことを全て自前で行ったのでその時のことを書こうと思いますが、ざっくばらんに書いているのでなんとなくこんなことしたなーと言うのが伝わればいいかなと思っています。
ツリー構造については事前知識があるとして書きます。書くのが面倒なのでわからないことはchatGPTにでも聞いてください
そしてネタよりになるので気に食わない方は今すぐブラウザバック推奨です！σ(･･￣　) ﾎｼﾞﾎｼﾞ

# 先にGemの紹介
ツリー構造のサポートGemがいっぱいあるので参考程度に載せておきます。
（自前実装後に以下のGem達に出会ったのですが時既にお寿司でした🍣）
- [acts_as_tree](https://github.com/amerine/acts_as_tree)（隣接リスト）
- [ancestry](https://github.com/stefankroes/ancestry)（経路列挙）
- [closure_tree](https://github.com/ClosureTree/closure_tree) （閉包テーブル）
- [awesome_nested_set](https://github.com/collectiveidea/awesome_nested_set) （入れ子集合）

調べたらもっと色々あるかもなんで自分で調べろください。

# なぜ隣接リストモデルを閉包テーブルにしたのか？
はい。まずここですよね。
なぜかと言うとHubbleではあるDBで隣接リストモデルを採用している部分がありました。
それ自体は問題ないのですが、隣接リストモデルの都合上データが増えれば増えるほど配下の取得に時間がかかりますよね。
今回対象となった部分はあるデータの取得に1分ほどかかっていました（えぐいですね）
取得方法は以下のように再起的に呼んでいました。
```rb
# BlackKnight Model
def subordinate_knight(knights = [])
  BlackKnight.where(master_id: id).find_each do |knight|
    knights.push(knight)
    knight.subordinate_knight(knights)
  end
    
  knights
end
```

例えば総司令のゼロが組織の人物を全員集めたいとします。
するとゼロが扇などの1階層下の配下一人ずつに「集合」といいます。
そして扇などがさらに1階層下の配下一人ずつに「集合」といいます。
これを一番下まで一人ずつ繰り返すのです。
想像してみてください。
こんなんじゃ時間がかかりすぎて世界を壊すことができません。

「ああ・・・ 俺は・・・ 世界を・・・壊し 世界を・・・創る・・・」

# 本題
まずはBlackKnightに対する閉包モデルを作成し、関連を書きます。

```scheme
create_table "closure_trees", force: true do |t|
  t.bigint "black_knight_id", null: false
  t.bigint "closure_tree_black_knight_id", null: false
  t.integer "hierarchy", null: false
end
```

```rb
class ClosureTree < ApplicationRecord
  belongs_to :black_knight
  belongs_to :closure_tree_black_knight, class_name: BlackKnight.name.to_s

  validates :hierarchy, presence: true
  validates :black_knight, uniqueness: { scope: %i[hierarchy closure_tree_black_knight] }
end
```

そしてBlackKnightにも関連を追加します
```rb
class BlackKnight < ApplicationRecord
  has_many :closure_trees, dependent: :destroy
  has_many :child_closure_trees, class_name: "ClosureTree", foreign_key: "closure_tree_black_knight_id", dependent: :destroyend
end
```

次にBlackKnightのCRUD時にClosureTreeを更新する処理を書きます。
```rb
# BlackKnight Model
after_save :update_closure_trees

def update_closure_trees
  # ルルは-1
  if master_id
    parent_closure_tree = ClosureTree.where(black_knight_id: master_id).order(hierarchy: :asc).to_a

    closure_tree = ClosureTree.new(black_knight_id: id)
    import_closure_tree = parent_closure_tree.map do |pbk|
      closure_tree.closure_tree_black_knight_id = pid.closure_tree_black_knight_id
      closure_tree.hierarchy = pid.hierarchy
      closure_tree.dup
    end
    closure_tree.closure_tree_black_knight_id = id
    closure_tree.hierarchy = parent_closure_tree.size + 1
    import_closure_tree << closure_tree.dup

    ClosureTree.import!(import_closure_tree)
  else
    closure_trees.create!(closure_tree_black_knight_id: id, hierarchy: 1)
  end
end
```

今回はコールバックで実行しています。
そして細かい記述やバリデーションはプロダクトごとに必要な条件が変わるので省きます。
注意点としてはまとめてBlackKnightを更新する時などはコールバックでやると結構な処理が追加で必要になりまが、適宜controllerなどでやる場合はそれを管理するコストもあります。
適宜でよろしくてよ

# データ取得の変更
```rb
black_knight_ids = ClosureTree.joins(:black_knight)
                              .where(closure_tree_black_knight_id: id)
                              .pluck(:black_knight_id)
BlackKnight.where(id: black_knight_ids)
```
これで[なぜ隣接リストモデルを閉包テーブルにしたのか？](#なぜ隣接リストモデルを閉包テーブルにしたのか？)であった問題が解消されました。
例えば総司令のゼロが組織の人物を全員集めたいとします。
ゼロが配下全員に一度だけ「集合」といいます。
すると黒の騎士団全員が一気に集まります。
でめたしでめたし

# 既存データの更新
既存データをrakeなどで更新します。
```rb
class CreateClosureTree
  def execute
    all_black_knights = BlackKnight.pluck(:id, :master_id)
    black_knights = BlackKnight.where.missing(:closure_trees)
                               .pluck(:id, :master_id)

    black_knights.each_slice(1000) do |es|
      es.each do |ids|
        if ids[1] == -1
          ClosureTree.create!(black_knight_id: ids[0], closure_tree_black_knight_id: ids[0], hierarchy: 1)
        else
          target_black_knight = ids
          master_ids = [ids]
          until target_black_knight[1] == -1
            target_black_knight = all_black_knights.find { |all_black_knight_ids| all_black_knight_ids[0] == target_black_knight[1] }

            master_ids << target_black_knight
          end

          closure_tree = ClosureTree.new(black_knight_id: ids[0])

          closure_trees = master_ids.reverse.map.with_index(1) do |m_id, i|
            closure_tree.closure_tree_black_knight_id = m_id[0]
            closure_tree.hierarchy = i
            closure_tree.dup
          end

          ClosureTree.import!(closure_trees)
        end
      end
    end
  rescue StandardError => e
    p e.message
    p e.backtrace
  end
end

CreateClosureTree.new.execute
```

実装中の私
私「こいつを回せば終了！！！！！」
ぽちーーーーーーーーーーーっ
結果「ERROR!!!!!!!!!!!!!!!!!!!!!!」
どこのDBにも存在する不整合データでエラーになりました。
今回は省きますがそれらを考慮する必要がありますので適宜対応願います。
上記のrakeは殴り書きしたので変数名とか色々やばくてツッコミがあると思いますが許してください。

# 最後に
これで神聖ブリタニア帝国から日本を取り戻せそうです。
いつから**隣接リストモデルを閉包テーブルに変更したった**話だと思っていたのか？

P.S. 実はこの件の対応は@ks01050320141989さんが他のリポジトリで既に実装済みのものをパクってきたので、私はほぼ脳死で実装することができました。
近々Hubbleで忘年会があるのでその時にお礼の一つでもしたいと思います。

明日は @taamoo2  さんです！