https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D0%B8_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B5_space_filling_curves 2026-06-06T18:17:59Z История изменений этой страницы в вики MediaWiki 1.45.3 https://www.wikicshse.ru/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D0%B8_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BD%D0%B0_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B5_space_filling_curves&diff=1466&oldid=prev 2018-10-15T11:55:40Z

<p>Новая страница: «{{Карточка_командного_проекта |name=Методы индексации данных на основе space filling curves |company=Янд…»</p> <p><b>Новая страница</b></p><div>{{Карточка_командного_проекта<br /> |name=Методы индексации данных на основе space filling curves<br /> |company=Яндекс<br /> |semester=Осень 2018<br /> |course=3-4<br /> |number_of_students=?<br /> |categorize=yes<br /> }}<br /> <br /> <br /> В ClickHouse, данные в таблицах семейства MergeTree, хранятся в наборе кусков, каждый из которых физически упорядочен по первичному ключу (такой ключ называют &quot;&quot;clustered index&quot;&quot;). Первичным ключом может быть произвольный кортеж из столбцов и выражений над ними (данные по кортежу упорядочиваются лексикографически). Это позволяет эффективно читать данные по диапазону ключа, так как уменьшает количество случайных чтений с дисков.<br /> <br /> Часто при проектировании базы данных в ClickHouse, трудно выбрать порядок столбцов ключа в кортеже. Для примера, в базе данных рекламной системы, ключевыми столбцами является идентификатор рекламодателя (кто заказывал рекламу) и идентификатор рекламной площадки (на каком сайте размещена реклама). Отчёты надо строить иногда для рекламодателя, а иногда - для рекламной площадки. То есть, первым столбцом в ключе может быть или тот, или другой идентификатор. В этом случае разумным является выбрать такой порядок столцбов, от которого будут выигрывать большинство запросов; а другие запросы будут выполняться медленно. Либо хранить таблицу в двух вариантах (копиях).<br /> <br /> Тем не менее возникает вопрос - можно ли упорядочить данные по некоторому отношению порядка, которое будет средним (компромиссным) между несколькими вариантами, и будет работать хорошо в обеих случаях? Ответом на этот вопрос являются space filling curves. https://en.wikipedia.org/wiki/Z-order_curve В результате, если данные упорядочивать по z(attr1, attr2...), то мы получим нечто среднее между упорядочиванием данных по одному атрибуту и по другому атрибуту.<br /> <br /> Для реализации предстоит решить несколько проблем.<br /> <br /> 1. Если в таблице ключом является выражение z(x, y), то индекс должен работать, если в запросе указано условие на x или на y. Для этого потребуется уметь вычислять обратное отображение диапазонов для некоторых функций.<br /> 2. Равномерному смешиванию локальности расположения данных может мешать неравномерность распределения значений смешиваемых атрибутов. Для того, чтобы это обойти, мы будем вычислять space filling curve с некоторыми хитрыми эвристиками.</div>

imported>Aapoludnitsin