За последние 24 часа нас посетили 52288 программистов и 1722 робота. Сейчас ищут 835 программистов ...

Алгоритм сортировки в MySQL

Тема в разделе "Решения, алгоритмы", создана пользователем Raadset, 19 май 2022.

  1. Raadset

    Raadset Новичок

    С нами с:
    19 май 2022
    Сообщения:
    3
    Симпатии:
    0
    Здравствуйте.

    На днях прочитал о различных алгоритмах сортировки и меня заинтересовал вопрос каким алгоритмом сортируются данные в MySQL, но, к сожалению, я не нашёл ответа на этот вопрос в поиске и решил обратиться с ним к профи.

    Если кто-то знает каким алгоритмом сортировки пользуется MySQL, пожалуйста расскажите, было бы очень интересно узнать.
     
  2. mkramer

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.600
    Симпатии:
    1.764
    Там наверняка комбинация каких-то достаточно сложных алгоритмов, с учётом индексов и прочее. Но в целом люди пользуются базами данных, чтоб НЕ думать о том, каким там алгоритмом сортирует MySQL, а просто писать ORDER BY и радоваться.

    Там, где имеет смысл задумываться о способах хранения или других механизмов, документация указывает разницу, и как выбрать.
     
    Sail нравится это.
  3. Raadset

    Raadset Новичок

    С нами с:
    19 май 2022
    Сообщения:
    3
    Симпатии:
    0
    И всё же, хотелось бы узнать какие алгоритмы используются, ведь есть множество типов сортировки: Сортировка пузырьком, Шейкерная сортировка, Сортировка расческой, Сортировка вставками, Сортировка Шелла, Сортировка деревом, и прочие...

    Я предполагаю используются только несколько предпочтительных алгоритмов. Хотя с другой стороны если взять, к примеру, каждый из алгоритмов сортировки и протестировать, то они будут работать куда медленней алгоритма сортировки в MySQL.
     
  4. mkramer

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.600
    Симпатии:
    1.764
    @Raadset Там всё намного сложнее, чем в перечисленных алгоритмах (это всё достаточно простенькие алгоритмы), MySQL при сортировке учитывает очень много всего, чтобы работать эффективно. Я не думаю, что хоть одному человеку на этом форуме приходило в голову шерстить сложнейший исходник mysql, с целью выяснить, а вдруг там сортировка пузырьком :)

    Знание этих алгоритмов хорошо, пока ты учишься. Чтоб мозги начали понимать, как составляются алгоритмы. В реальных программах никто и никогда не будет писать пузырьковую сортировку, да вообще думать о сортировке. Нужна сортировка массива - есть usort, ksort и прочее. Нужно отсортировать вывод из БД - есть ORDER BY.
     
  5. Raadset

    Raadset Новичок

    С нами с:
    19 май 2022
    Сообщения:
    3
    Симпатии:
    0
    То есть, вы хотите сказать что ни вы, и скорее всего никто на этом форуме, не сможет рассказать в общих чертах как работает эта сортировка? Мне и в голову не приходит как можно осуществить сортировку не сравнивая одно с другим через какой-то цикл.
     
  6. miketomlin

    miketomlin Старожил

    С нами с:
    9 авг 2016
    Сообщения:
    3.861
    Симпатии:
    657
    Поэтому вы и задаете такие нелепые вопросы. СУБД/БД изначально устроена так, чтобы быстро искать. Т.е. в ней используются «избыточные» структурные данные, не относящиеся непосредственно к хранимому контенту. Почитайте про бинарные деревья, хэш-таблицы и т.п. Так что ваши сортировки «чистых» данных плохо соотносятся с тем, как работает СУБД. Можно сказать, что там данные хранятся в уже отсортированном виде ;)
     
  7. iceblood

    iceblood Активный пользователь

    С нами с:
    20 фев 2020
    Сообщения:
    83
    Симпатии:
    12
    Можешь зайти https://github.com/MariaDB/server/tree/10.9/mysys
    и почитать комментарии в файлах
    mf_qsort.c
    mf_qsort2.c
    mf_sort.c

    mf_qsort.c:
    Код (Text):
    1. /*
    2.   qsort implementation optimized for comparison of pointers
    3.   Inspired by the qsort implementations by Douglas C. Schmidt,
    4.   and Bentley & McIlroy's "Engineering a Sort Function".
    5. */
    Вообще, то что тебя интересует называется "Алгоритмы и структуры данных"

    В общих чертах выглядит так:
     
    #7 iceblood, 31 май 2022
    Последнее редактирование: 31 май 2022
  8. iceblood

    iceblood Активный пользователь

    С нами с:
    20 фев 2020
    Сообщения:
    83
    Симпатии:
    12
  9. Dimon2x

    Dimon2x Старожил

    С нами с:
    26 фев 2012
    Сообщения:
    2.211
    Симпатии:
    186
    Но на собесах могут спросить, да?
     
  10. mkramer

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.600
    Симпатии:
    1.764
    Я не спрашиваю. Но тут от интервьювера зависит, от конторы. Если и спрашивать про алгоритмы, то не про пузырёк, естественно. Вот деревья, графы - это могут спросить скорее, потому что это используется.
     
  11. Dimon2x

    Dimon2x Старожил

    С нами с:
    26 фев 2012
    Сообщения:
    2.211
    Симпатии:
    186
    @mkramer джуну надо знать деревья?
     
  12. mkramer

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.600
    Симпатии:
    1.764
    Интервьювер строит тех. собеседование в зависимости от того, чем занимается фирма. Если специализируется на несложных сайтах - то нафиг оно там не надо.
    --- Добавлено ---
    Вообще, у нас бинарное дерево было лабой на первом курсе :)
     
  13. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.128
    Симпатии:
    1.248
    Адрес:
    там-сям
    джуну надо уметь писать код, в первую очередь. у тебя именно с этим проблемы - ты не стартуешь. а деревья и другие структуры конечно помогают. человек с широкими знаниями может писать лучший код / более быстрый код / безошибочный код )))