Давно я не писал ничего в свой блог, а потому у меня было время посмотреть, какие статьи накопились в разделе для начинающих программистов. Я решил уделить чуть больше времени практике и поразбирать задачи, которые люблю давать на собеседованиях сам и которые дают мои коллеги. Решая задачу, не спешите сразу же смотреть решение. Попробуйте минут 15 подумать. Можете даже написать мне наводящие вопросы вот тут. Потом сравните своё решение с тем, что предложено. Надеюсь, формат будет удобен и интересен моим читателям 😉
Задача не прямо чтобы простая, но и не уровня Хабра. Вообще, я не очень люблю давать людям заумные задачи в без того стрессовой атмосфере. Мне больше интересно посмотреть на то, как человек думает и строит свои мысли, чем на то, как он умеет решать олимпиадные задачи.
У Вас есть следующие вводные:
1. Есть новостной сайт, который показывает новости в каком-то порядке (это не столь важно для задачи)
2. Перейдя по ссылке /news/123, Вы откроете страницу новости с ID 123, на которой будет располагаться заголовок новости, её тело и лента комментариев
3. Комментарии идут от самого нового к самому старому. Пусть пока в них не будет ветвления.
Задачи:
1. Спроектировать хранение новостей и комментариев в реляционной БД.
2. Организовать удобный вывод комментариев к новости.
Показать решение
Поскольку у нас есть две сущности (Новость и Комментарий), то нам потребуется две таблицы для хранения непосредственно их без связки между собой. Из постановки задачи следует, что у одной новости может быть несколько комментариев, поэтому связь будет «один-ко-многим». Из этого следует, что создавать третью таблицу для связки не нужно — достаточно будет только указать в таблице Комментариев ID новости, к которой привязан конкретный комментарий.
Теперь стоит расписать таблицы точнее. Здесь можно немного порисовать, чтобы получить примерно следующую картинку
Если присмотреться, то мы увидим, что на схеме не хватает таблицы пользователей. В рамках задачи её можно опустить, так как для выполнения условий вполне достаточно наличия ссылки на пользователя в виде его ID, но в реальной системе разумеется эта связь должна быть на месте.
Чего здесь действительно не хватает, так это индексов. Перво-наперво, нужно обозначить первичные ключи. Дальше стоит обратить внимание на поля, которые будут нуждаться в индексах. Здесь нужно вспомнить пару правил присвоения индексов при разработке системы. Индексы с ходу нужны там, где
- Поле используется в качестве фильтра в WHERE
- Поле является связующим в JOIN
У нас это поля id_news и id_user в таблице comments. При этом, если очень хочется совсем правильного решения, то можно сделать эти ключи внешними. Только не забудьте принципы их работы, ведь Вас наверняка спросят о том, чем обычный индекс отличается от внешнего ключа.
В итоге у нас получится уже обновлённая картинка, где уже видны связи (внешние ключи в comments имеют фиолетовый маркер).
Разумеется, при рассуждениях Вам будут задавать дополнительные вопросы, и Вы должны быть к ним готовы. Это могут быть вопросы рода:
- Какие типы индексов Вы знаете?
- Как быть, если комментарии нужно выводить в виде дерева?
- Какую СУБД Вы бы использовали и почему?
Следующий вопрос уже с подвохом. Сама задача содержит определение «удобный вывод», поэтому прежде чем бросаться за проектирование, нужно задать наводящие вопросы. Что есть «удобный вывод»? Скорее всего, это UI, который показывает по N комментариев, подгружая остальные посредством AJAX.
Вероятно Вас попросят написать простенький JS-код, который будет отвечать за подгрузку новостей (если хотите проверить себя, смело присылайте мне свои варианты через форму обратной связи!), но основная соль задачи в том, чтобы разобраться с пошаговой выдачей комментариев. Именно в ней таится основной подвох задачи.
Самое явное решение здесь в том, чтобы ответить: «Мы будем отдавать комментарии по ID новости и номеру подгружаемой порции, используя SQL-конструкцию LIMIT с указанием offset». Запрос будет выглядеть примерно вот так:
Кажется, что это тривиальное решение уже не отделяет Вас от успешного завершения данной задачи. Но не тут-то было. Если для решения Вы выбрали MySQL, то загвоздка состоит в том, что такая конструкция будет хорошо работать на небольших сайтах. Если же у Вас количество комментариев будет достаточно большим и измеряться десятками тысяч, то загрузка новых страниц будет тормозить сильнее и сильнее. Если мы получим конструкцию LIMIT 100000, 25, то MYSQL будет пробегать все 100000 строк, а только затем возвращать Вам ограниченные 25. Это известная проблема, и решений тут много. Например, можно решить эту проблему на уровне кода.
Одно из возможных решений состоит в том, чтобы отсекать «хвост» комментариев через условие WHERE, которое будет фильтровать записи по ID комментария, который был последним в предыдущем пакете комментариев, отправленных пользователю. Нас интересуют комментарии в порядке их старения, а значит, если пользователю уже был показан комментарий с ID, например 10000, то все ID > 10000 будут содержать только более новые комментарии (ведь ID — это автоинкрементальное поле). Значит при каждом новом запросе мы должны будем добавлять в запрос условие
У Вас могут спросить, есть ли другие решения для данной задачи. Ещё одно решение базируется на чистом перестроении запроса
Хитрость здесь состоит в том, что для построения ограниченной выборки MySQL в таком случае уже не лезет в саму таблицу, а начинает принудительно строить выборку по более быстрым индексам, так как работа уже идет с вложенным запросом. Но это особенность исключительно MySQL. В других СУБД оптимизатор работает иначе.
Надеюсь, что статья была для Вас интересна и полезна! Я постараюсь уделять время разбору и других интересных задач. Буду рад, если Вы тоже будете присылать мне задачи, с которыми столкнулись на собеседованиях для того, чтобы мы разобрали их решение здесь.