Сложность обратного поиска внешнего ключа django

Question

Предположим, у меня есть такая модель:

    class Post(models.Model):
         name = models.CharField(max_length=25, unique=True)

    class Picture(models.Model):
         post = models.ForeignKey(to=Post, ondelete=models.CASCADE)
         image = models.ImageField()

Теперь предположим, что я делаю запрос примерно так:

    p = Post.objects.get(name=foo)
    images = p.picture_set.all()

Теперь первый запрос явно просматривает все сообщения, чтобы получить тот, который имеет имя foo,
Но я хотел бы знать о втором. Поиск по всем Picture Таблица в базе данных, чтобы найти все фотографии, которые имеют post=p или информация доступна, когда я получаю p в первом запросе?
Потому что если это первое, то меня беспокоит проблема масштабируемости.

Answer 1

Но я хотел бы знать о втором. Проводится ли поиск по всей таблице изображений в базе данных, чтобы найти все изображения, имеющие post = p, или информация доступна, когда я получаю p в первом запросе?

Краткий ответ: по умолчанию ForeignKey добавляет индекс, делая поиск довольно быстрым (логарифмическое по количеству значений и линейное по количеству обратных записей).

Это зависит от того, строит ли база данных индекс на ForeignKey, По умолчанию Django создаст индекс. Это означает, что он хранит не только строки таблицы, но также структуру данных, которая позволяет быстро искать все строки, имеющие определенное значение.

Реализация индекса может зависеть от базы данных. В MySQL по умолчанию будет использоваться BTREEэто означает, что для поиска значения требуется приблизительно O(log n), чтобы получить коллекцию, и O(k) с k количеством элементов с этим внешним ключом, чтобы получить все. Но существуют и другие структуры индекса, такие как какая-то хеш-таблица, которая даже позволяет (немного) ускорить поиск, хотя, например, хеш-таблица не будет настолько эффективной для извлечения всех элементов с ForeignKey меньше заданного числа.

Вы также можете добавить индекс для других столбцов, например:

class Post(models.Model):
    name = models.CharField(max_length=25, db_index=True, unique=True)

Так что теперь извлекаю все Post объекты с именем с заданным именем также будут работать быстрее.

Использование индексов, конечно, не "бесплатно": это означает, что каждый раз, когда вы вставляете или удаляете запись, индекс также должен быть изменен (обычно для этого также требуется O(log n)). Если вы обновляете запись, изменяя значение внешнего ключа, этот индекс также необходимо изменить. Таким образом, индексы обеспечивают значительное ускорение, но следует стремиться размещать индексы только в столбце, для которого часто выполняется поиск, поскольку в противном случае стоимость "обслуживания" индекса может быть больше, чем выигрыш от ускорения процесса поиска.