隣接リストが使える場合って?
最近階層構造について考える機会があったので、隣接リストについてお話したいと思います。
隣接リストはアンチパターンとして名高いですが、条件を満たせば使っても良いものかと思いますので今日は前向きに隣接リストを擁護していきたいと思います笑
使って良い条件とは、、、?
ざっくり、3点に当てはまれば使ってもよいかなーと思います。
- 階層の数が固定である
- ノードの移動がない
- 簡易的でいいのでサクッと作りたい
1.階層の数が固定である
rootとリーフ(最上位層と最下層)が追加になる分には変更コストが少ないですが、中間にノードが追加される場合には、データの変更コストがかかるので、階層構造が変わりやすい場合には向かないでしょう。ノードが追加になることで、子のデータも変更する必要が出てくるためです。
2.ノードの移動がない
1と似ていますが、ノード自体が頻繁に移動する場合にもデータの変更コストがかかるので、やめたほうがよいでしょう。
3.簡易的でいいのでサクッと作りたい
一番の弱点は拡張性がないことかと思っています。
色々な制約ができることと引き換えにスピードを優先するのも一つの戦略ではないでしょうか?
また、すべて取得するには階層数に合わせてjoinして取得する必要がありますが、
子が列に追加されていくことになり、アプリケーション側で使いづらいかもしれません。
注意事項
その時作ったシステムが未来永劫そのまま使われるということは少ないのではないでしょうか?
階層構造が大きく変わるタイミングが訪れた際には、その時に求められる要件を満たした上で、少ない工数、運用コスト、拡張性等考慮した上で最適な設計を選ぶということが大切だと思います。
最後に
スペースマーケットでは、一緒にサービスを成長させていく仲間を探しています。
ビジネスサイド、エンジニアメンバー共に話しやすいメンバーが多く非常に働きやすい環境だと思います!
ご興味ある方ぜひ見てみて下さい!
スペースを簡単に貸し借りできるサービス「スペースマーケット」のエンジニアによる公式ブログです。 弊社採用技術スタックはこちら -> whatweuse.dev/company/spacemarket
Discussion