Redmineのデータ構造が "素晴らしい" 話

Transcript

1. Redmineのデータ構造が "素晴らしい" 話 北亜 - Hokua
2. 自己紹介 • 北亜 - ほくあ ◦ @Hokua_82 • Ruby歴 9年 ◦ (まともに書いてるのは) 約2年 • 本業 ◦ Rails / React / erb など…… • VRChat ◦ チュートリアル2周目終 ◦ アバター：しなの/真冬
3. Redmine • プロジェクトマネジメントツール ◦ Ruby on Rails製 • Rubyのチケット管理とかでも使われてたりします ◦ https://bugs.ruby-lang.org/
4. Redmineの特徴 • 無限に作れる親子 階層 • 深さ上限なしで「無 限に」深い親子階層 が作れる ◦ チケット ◦ プロジェクト ◦ etc……
5. 親子階層が無限 • シンプルに作るなら各チケット(Issue)が parent_id を保持する形が良さそう • 問題点は取得 ◦ チケットの親子階層を解決しようと思うと、クエリを何度も発行する必要がある • 「隣接リスト」と呼ばれている
6. Redmineの"素晴らしい"解決 - Nested Sets (入れ子集合) • 木構造を作りたい • 各Issueに左端(lft)と右端(rgt)の情報を持たせる • 親の lft , rgt の内側にあるIssueをそのIssueの子孫として扱 う。
7. Nested Sets - 入れ子集合 (2)
8. Nested Sets - 入れ子集合 (3)
9. Nested Setsが得意なこと • 取得が早い • 1クエリで子孫を全て取得可能
10. ここが辛いよ Nested Sets UPDATEが地獄 追加位置の lftより 右のチケットを全て 更新する必要がある
11. 終わり • DB構造によって得意なことは変わる ◦ Nested Sets ▪ GETは得意 ▪ UPDATEは苦手 ◦ 隣接リスト ▪ GETは苦手 ▪ UPDATEは得意 • サービスの特性によって"素晴らしい"データ構造は変わる 参考資料： Bill Karwin『SQLアンチパターン 第2版』オライリー・ジャパン、2025年