Производительность обхода одного уровня индекса зависит от структуры данных. Если индекс с ключами фиксированной длины и с фиксированным значением (что часто используется в sql-based субд, там значение - это номер записи в массиве записей), то можно вычислить положение любой внутренней ссылки в блоке и использовать например поиск методом половинного деления. Если ключи переменной длины, то это уже невозможно, приходится проходить по блоку сначала в том же направлении сортировки, в котором он был построен (неважно, по возрастанию или убыванию). Будет там компрессия или нет - это уже не важно. Если применяется компрессия для составных ключей каждый фрагмент которого пусть даже фиксирован, проходить придется также в направлении сортировки при построении. Если в индексе ключи фиксированной длины, а значения переменной, то проходить также придется в направлении сортировки. Если требуется перечисление в обратном порядке, то придется пройти вперед, проскочить нужный, выяснить что проскочили и вернуться обратно. То же самое относится к операции $query. Но $order намного усложняется если ключи еще и с компрессией, потому что искомое значение может оказаться как в пройденном предыдущем, так и в дописанном хвосте. Те, кто особенно внимательно изучали mssql, могли заметить в документации оговорку, что выборка по индексу производится быстрее если desc или asc в операции order by совпадает с desc или asc используемом при построении индекса. Что касается right link и left link в блоках cache и msm - то это для переливов при балансировке. Переливы конечно упрощаются, но поддержание согласованных уровней имеет и отрицательную сторону - простенькая операция изменения базы (неважно, вставка, перезапись или удаление) может привести к перестроению совершенно невиновных блоков и к отметке об их модифицированности, что снижает ценность кеша. Впрочем, нам это только одно теоретизирование, повлиять на структуру базы каше мы вряд ли сможем. Хотя в стандарте не оговаривается в каком именно порядке должны храниться ключи, обычно все М системы хранят все глобалы в одной сортировке. В sql системах в зависимости от реализации можно повлиять на сортировку в структуре индекса. Можно даже попробовать побарствовать и иметь два индекса отличающиеся направлением сортировки.

Некоторые материалы можно найти тут
http://drus.boom.ru/Science.htm