ツリー構造をもつコメント・リプライ機能の実装

Posted at 2024-06-02

はじめに

Django REST FrameworkでTwitterもどきを個人開発しています。

この記事では、django-treebeardというツリー構造に特化した、ライブラリを使用して、ツリー構造をもつコメント・リプライ機能を実装します。
またdjango-treebeardを理解するうえで調べた、階層構造の表現方法についても記載しています。

django-treebeardについて

以下は公式のdjango-treebeardについての説明を翻訳したものです。

django-treebeardは以下の特徴を持ちます：

柔軟性: 同じAPIで3つの異なるツリー実装を含みます：
1. 隣接リスト (Adjacency List)
2. 経路列挙 (Materialized Path)
3. 入れ子集合 (Nested Sets)
高速性: 最適化された非ナイーブなツリー操作
簡単: 抽象クラスを使用して独自のモデルを定義するDjangoモデル継承を使用
クリーン: テスト可能で十分にテストされたコードベース。コード/ブランチのテストカバレッジは96%以上

隣接リスト (Adjacency List)、経路列挙 (Materialized Path)、入れ子集合 (Nested Sets)をちょっと調べた感じ、難しくてあきらめそうになりました。
どれもツリー構造やグラフ構造、階層構造を表現するための方法です。
django-treebeardでは上記3つの実装方法が用意されていて、実装者がどの実装方法をとるか選べます。
以下ざっくりとした説明を載せます。

隣接リスト (Adjacency List)とは？

隣接リスト (Adjacency List)は、各ノード（要素）が自分の「親ノード」を参照することで、ノード同士の関係を表します。
つまり子が親を知っているということで、階層構造を表しているみたいです。

隣接リスト (Adjacency List)のメリット

各ノードは自分の親ノードを知っているだけなので、データ構造がシンプル
各ノードは一つの参照（親ノード）しか持たないため、メモリを効率的に使用できる

隣接リスト (Adjacency List)のデメリット

深さや子孫ノードの検索が非効率
- すべての子孫を検索するには再帰的に親子関係をたどる必要があるため
データ更新の際の複雑さ
- ノードの挿入や削除、移動などの操作が発生すると、その影響を受ける他のノードの親子関係も更新する必要があるため
木構造の整合性チェックが難しい
- ノードの参照が壊れたりした場合、ツリー全体の整合性が崩れることがあるため

経路列挙 (Materialized Path)とは？

経路列挙 (Materialized Path)は、各ノード（要素）がツリー内で自分がどの位置にいるかを「パス（道筋）」として記録します。

クラブ活動の組織図の場合は以下の通り「パス（道筋）」を割り当てます。
各ノード（要素）がツリー内で自分がどの位置にいるかを「パス（道筋）」として記録すると以下の通りになります。
メンバー1のパスはRoot.A.A1.A1.1で文字通り、すべての道筋を保持します。

クラブ全体 (Root) -> "Root"
- 部門A (A) -> "Root.A"
  - チーム1 (A1) -> "Root.A.A1"
    - メンバー1 (A1.1) -> "Root.A.A1.A1.1"
    - メンバー2 (A1.2) -> "Root.A.A1.A1.2"
  - チーム2 (A2) -> "Root.A.A2"
    - メンバー3 (A2.1) -> "Root.A.A2.A2.1"
- 部門B (B) -> "Root.B"
  - チーム1 (B1) -> "Root.B.B1"
    - メンバー4 (B1.1) -> "Root.B.B1.B1.1"

経路列挙 (Materialized Path)のメリット

検索や追加、削除が簡単
- 例えば、部門Aに所属するすべてのメンバーを検索する場合、「Root.A」で始まるパスを持つすべてのノードを探せばよいので、簡単です
- 追加の場合、そのノードのパスを親ノードのパスに追加するだけで済みます
- 削除も「Root.A」で始まるパスを検索して、削除できます
階層の把握が容易

経路列挙 (Materialized Path)のデメリット

パスの更新が必要
- ツリー構造内でノードを移動させる場合、移動するノードだけでなく、そのノード以下のすべての子ノードのパスを更新する必要があるため、特に深いツリーや大規模なツリー構造においては更新操作が重くなる
パスの長さ
- パスの長さがツリーの深さに比例して長くなるため、非常に深いツリー構造を持つ場合、パス情報が大きくなり、データベースのサイズや検索の効率に影響を与える可能性がある

入れ子集合 (Nested Sets)とは？

これが一番理解するのが難しかったです。。
各ノードに「左値」と「右値」という2つの数値を割り当てることで、ツリー内での位置や親子関係を表します。

クラブ活動の組織図の場合は以下の通り左値（L）と右値（R）を割り当てます。
（割り振り方については調べてみてください。自分はchat-GPTに効きました）

クラブ全体 (Root) [L=1, R=14]
- 部門A (A) [L=2, R=9]
  - チーム1 (A1) [L=3, R=6]
    - メンバー1 (A1.1) [L=4, R=5]
  - チーム2 (A2) [L=7, R=8]
    - メンバー3 (A2.1) [L=8, R=9]
- 部門B (B) [L=10, R=13]
  - チーム1 (B1) [L=11, R=12]
    - メンバー4 (B1.1) [L=12, R=13]

入れ子集合 (Nested Sets)のメリット

子ノードの検索が高速

入れ子集合 (Nested Sets)のデメリット

子供の追加や親の変更が複雑
理解しづらい

Ex:閉包テーブル（Closure Table）

django-treebeardにはない実装方法ですが、よく上記3つとともに比較されているのでこちらも理解しておこうと思います。
閉包テーブルは、すべての親子関係を直接テーブルに保存することで、階層構造の検索を効率的に行うことができます。

さきほどのクラブ活動の組織図の場合は

クラブ全体 (Root)
- 部門A (A)
  - チーム1 (A1)
    - メンバー1 (A1.1)
    - メンバー2 (A1.2)
  - チーム2 (A2)
    - メンバー3 (A2.1)
- 部門B (B)
  - チーム1 (B1)
    - メンバー4 (B1.1)

以下の通り、ノード同士の親子関係をすべて記録するテーブルを追加します。

親ノード	子ノード
Root	Root
Root	A
Root	A1
Root	A1.1
Root	A1.2
Root	A2
Root	A2.1
Root	B
Root	B1
Root	B1.1
A	A
A	A1
A	A1.1
A	A1.2
A	A2
A	A2.1
B	B
B	B1
B	B1.1
A1	A1
A1	A1.1
A1	A1.2
A2	A2
A2	A2.1
B1	B1
B1	B1.1

閉包テーブル（Closure Table）のメリット

クエリの効率化
- 親子関係をすべて記録しているため、特定のノードのすべての子孫ノードや祖先ノードを簡単に検索できる
構造の柔軟性
誤ったデータが入りにくいため、一貫性が保持しやすい

閉包テーブル（Closure Table）のデメリット

更新操作が複雑で時間がかかる

実装編

前提

Django REST Frameworkがインストールされていること
django-treebeardがインストールされていること

注意事項

個人開発途中のソースのため、Userや認証機構など作成済みのコードが含まれます
ほとんどのコードがchat-GPTが作成したものです
python,DRFの経験が浅いため、ベストプラクティスから外れている可能性があります

Tweetモデルの作成

MP_Nodeを継承した、Tweetモデルを作成します。
MP_Nodeは前述した、Materialized Pathでの実装方法となります。

models.py

class Tweet(MP_Node):
    user = models.ForeignKey(User, on_delete=models.CASCADE)
    content = models.TextField()
    created_at = models.DateTimeField(auto_now_add=True)

    node_order_by = ['created_at']

    def __str__(self):
        return self.content[:50]

    class Meta:
        indexes = [
            models.Index(fields=['user']),
            models.Index(fields=['created_at']),
        ]

マイグレーションを実行します。

python manage.py makemigrations
python manage.py migrate

作成されたテーブルは以下図になります。
pathがツリー内で自分がどの位置にいるかの「パス（道筋）」を保持するカラムになります。
depthとnumchildはdjango-treebeardが、検索速度を向上させるために追加しているカラムです。

Serializerの作成

serializers.py

class PostSerializer(serializers.ModelSerializer):
    class Meta:
        model = Tweet
        fields = ['content']

    def create(self, validated_data):
        user = self.context['request'].user
        if user is None or not user.is_authenticated:
            raise serializers.ValidationError("User is not authenticated")

        validated_data['user'] = user
        validated_data['created_at'] = datetime.datetime.now()
        return Tweet.add_root(**validated_data)


class ReplySerializer(serializers.ModelSerializer):
    parent_id = serializers.IntegerField(required=True, write_only=True)

    class Meta:
        model = Tweet
        fields = ['content', 'parent_id']

    def create(self, validated_data):
        # JWTからユーザー情報を取得し、Tweetに登録する
        user = self.context['request'].user
        if user is None or not user.is_authenticated:
            raise serializers.ValidationError("User is not authenticated")
        validated_data['user'] = user
        validated_data['created_at'] = datetime.datetime.now()

        # リクエストから親のTweetIDを取得し、親Tweetを検索
        parent_id = validated_data.pop('parent_id', None)
        parent_tweet = Tweet.objects.get(id=parent_id)

        return parent_tweet.add_child(**validated_data)


class TweetSerializer(serializers.ModelSerializer):
    class Meta:
        model = Tweet
        fields = ['id', 'content', 'created_at']

PostSerializer
- ツイート用(root)のSerializer
- add_rootメソッドを使用する
ReplySerializer
- ツイートに対するリプライのSerializer
- リプライに対するリプライもこちらのSerializerを使用
- 親ノードを取得後、add_rootメソッドを使用して、親子関係を紐づける
TweetSerializer
- 一覧取得用のSerializer

Viewの作成

views.py

class TweetCreateAPIView(CreateAPIView):
    queryset = Tweet.objects.all()
    serializer_class = PostSerializer
    permission_classes = [permissions.IsAuthenticated]
    authentication_classes = [JWTAuthentication]

    def perform_create(self, serializer):
        serializer.save(user=self.request.user)


class ReplyCreateAPIView(CreateAPIView):
    queryset = Tweet.objects.all()
    serializer_class = ReplySerializer
    permission_classes = [permissions.IsAuthenticated]
    authentication_classes = [JWTAuthentication]

    def perform_create(self, serializer):
        serializer.save(user=self.request.user)


class TweetListView(ListAPIView):
    serializer_class = TweetSerializer
    pagination_class = PageNumberPagination

    def get_queryset(self):
        queryset = Tweet.objects.all()
        queryset = queryset.order_by("created_at")

        return queryset


class TweetChildrenView(APIView):
    def get(self, request, pk, format=None):
        try:
            tweet = Tweet.objects.get(pk=pk)
        except Tweet.DoesNotExist:
            return Response(status=404)

        children = tweet.get_children()
        paginator = PageNumberPagination()
        paginated_children = paginator.paginate_queryset(children, request)
        serializer = TweetSerializer(paginated_children, many=True)
        return paginator.get_paginated_response(serializer.data)

TweetCreateAPIView
- ツイート用(root)のView
ReplyCreateAPIView
- ツイートに対するリプライのView
TweetListView
- 一覧取得用のView
TweetChildrenView
- 子供取得用ののView
- tweet = Tweet.objects.get(pk=pk)で取得し、tweet.get_children()で親ノードに紐づく子ノードを取得する

URLの作成

urls.py

urlpatterns = [
    path('post/', TweetCreateAPIView.as_view()),
    path('reply/', ReplyCreateAPIView.as_view()),
    path('list/', TweetListView.as_view()),
    path('<int:pk>/children/', TweetChildrenView.as_view()),
]

実行

Twiiterの出始めの頃は、「なう」ってつけるのが流行ったとか

リプライ

リプライ内容とともにparent_idをPOSTして、親と紐づけます。

ツイート一覧取得

{
	"count": 10,
	"next": null,
	"previous": null,
	"results": [
		{
			"id": 14,
			"content": "ツイートなう",
			"created_at": "2024-06-01T23:46:19.076294Z"
		},
		{
			"id": 15,
			"content": "リプライなう",
			"created_at": "2024-06-01T23:48:21.292202Z"
		},
		{
			"id": 16,
			"content": "ツイートなう2",
			"created_at": "2024-06-01T23:50:27.240946Z"
		},
		{
			"id": 17,
			"content": "ツイートなう3",
			"created_at": "2024-06-01T23:50:31.392280Z"
		},
		{
			"id": 18,
			"content": "リプライなう2",
			"created_at": "2024-06-01T23:50:48.042285Z"
		},
		{
			"id": 19,
			"content": "リプライなう3",
			"created_at": "2024-06-01T23:50:51.906427Z"
		},
		{
			"id": 20,
			"content": "リプライなう4",
			"created_at": "2024-06-01T23:51:05.855007Z"
		},
		{
			"id": 21,
			"content": "リプライなう5",
			"created_at": "2024-06-01T23:51:10.614758Z"
		},
		{
			"id": 22,
			"content": "リプライなう6",
			"created_at": "2024-06-01T23:54:42.046981Z"
		},
		{
			"id": 23,
			"content": "リプライなう7",
			"created_at": "2024-06-01T23:54:52.217122Z"
		}
	]
}

リプライ一覧取得

今回は一階層下の子供しか取得していませんが、dump_bulkメソッドを使用すれば、親に紐づくすべてに子供、孫を取得できるようになります。

{
    "count": 3,
    "next": null,
    "previous": null,
    "results": [
        {
            "id": 15,
            "content": "リプライなう",
            "created_at": "2024-06-01T23:48:21.292202Z"
        },
        {
            "id": 18,
            "content": "リプライなう2",
            "created_at": "2024-06-01T23:50:48.042285Z"
        },
        {
            "id": 19,
            "content": "リプライなう3",
            "created_at": "2024-06-01T23:50:51.906427Z"
        }
    ]
}

感想

django-treebeardを使うことで、簡単にツリー構造を実装できました。
というか、ツリー構造を実装できるライブラリがあることにびっくりしました。さすがPython。

そして、ツリー構造の表現方法が多く存在することも知らなかったです。。
最近アルゴリズムやデザインパターンの重要性を再認識することが多く、勉強しようと強く思いました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up