Что означает термин "кластерный индекс" в MySQL и как он работает?

В MySQL термин "кластерный индекс" относится к специальному типу индекса, который определяет порядок физического хранения данных в таблице. Кластерный индекс определяет, как строки данных в таблице будут упорядочены по значениям данного индекса. В отличие от некластерного индекса, который просто указывает на местоположение данных в таблице без изменения их порядка.

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

Однако некоторые запросы могут возвращать данные без сортировки, если они не использовали кластерный индекс или запрос не содержит запрос на сортировку данных. В таком случае MySQL может вернуть данные в том порядке, в котором они хранятся на диске, что может привести к неупорядоченному результату.

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

https://habr.com/ru/articles/141767/

Кластерный индекс... это на самом деле понятие крайне виртуальное. 
 
 Что такое обычный некластерный индекс? берём выражение индекса, считаем его значение для каждой записи, сортируем и пишем на диск. Получаем отдельную структуру, в которой выражение индекса сортировано. Когда потребуется искать заданное значение этого выражения, мы вместо просмотра от записи к записи сразу половинным делением быстренько найдём нужное значение, возьмём из него уникальный идентификатор записи, и обратимся за записью. Если в таблице 1000 записей, то для поиска заданного значения без индекса нам в среднем пришлось бы просмотреть 500 записей, а с индексом - всего 10. 
 
 Теперь что такое кластерный индекс... сначала почти то же. Берём выражение индекса, считаем его значение для каждой записи, сортируем и... а вот теперь не записываем по порядку эти значения с номерами соответствующих записей в отдельную структуру, а сами записи располагаем в этом порядке. Теперь, когда потребуется искать заданное значение этого выражения, мы вместо просмотра от записи к записи, как это было, когда записи не сортированы, сразу половинным делением быстренько найдём нужное значение. Но нам уже не надо получать номер записи и обращаться за ней - мы нашли саму нужную запись. 
 
 В MySQL (точнее, в используемом по умолчанию движке InnoDB) первичный индекс, во-первых, существует ВСЕГДА, во-вторых, определяется так (в статье, на которую дали ссылку, имеются неточности в пункте 2): 
 
 
Выглядит так, как будто это просто физическая сортировка данных по индексируемому полю.
 
 Фактически - именно так. 
 
 
Создаётся ли отдельная таблица или просто упорядочивается хранение существующих данных?
 
 Не создаётся. Но при изменении первичного индекса таблица полностью пересоздаётся с новым физическим порядком записей. 
 
 
Если данные упорядочиваются этим индексом, допустим по ID, то почему при select без сортировки данные могут возвращаться в произвольном порядке, а не отсортированные по ID по-умолчанию?
 
 Если не задан явно ORDER BY, сервер имеет право вернуть записи в любом порядке, как ему удобнее. В большинстве случаев, но не всегда, он будет возвращать записи в порядке чтения с диска... 
 
 Представь такой (на самом деле невозможный, но не суть) случай - ты запросил таблицу. Вторая половина её ещё лежит в кэше, а первая уже выдавлена оттуда данными другой таблицы, нужными для выполнения запроса. Конечно, наиболее оптимальным будет начать передачу данных клиенту с этих записей, а пока они передаются, подчитать остальные, и передать их позже. Вот тебе порядок-то и поломался... 
 
 === 
 
 PS. Кстати, правило выбора индекса, который будет использоваться в качестве кластерного, имеет неприятный побочный эффект. Если у некоторых полей, входящих в какие-то индексы, изменяется свойство NULLability, то это может привести к изменению того, какой из имеющихся индексов станет использоваться в качестве первичного по пункту 2. В результате мы получим невозможность использования INSTANT / INPLACE методов, и будет использован длинный COPY. Впрочем, ситуация такая крайне редка.