Какие вы знаете актуальные структуры данных которые можно использовать для индексации и хранения?

Question

[Юрий Ярош]

Нырнул в пространственную индексацию с головой, разобрался с всякими замутными cache-obvious lookahead array'ями и как с них строить различные пространственные, и не очень, иногда нечёткие, индексы. Особо понравились работы Майкла Бендера и Tokutek в этом направлении, но там ещё есть недочёты.

Можете пожалуйста посоветовать интересные структуры данных которые можно было бы использовать для индексации и хранения, возможно есть какие-то новые веяния которые я успел пропустить.

Ссылки на цитаты и публикации приветствуются.

Спасибо.

p.s. Не думаю что B-tree и LSM-tree актуальны.

Answer 1

[uvelichitel]

Если B-tree уже не торт почитайте про relaxed B-tree.
В тегах вопроса присутствуют реляционные базы данных. Tree и вообще иерархические структуры чужды реляционной алгебре, однако повсеместны. Исследованные workaround это - Adjacency list и nested sets

Comments

[Юрий Ярош]

Про relaxed B-tree для балансировки, и про удаление без балансировки многопроходных деревьев поиска в курсе уже очень давно, эта тема уже очень хорошо изучена и это вещи ещё с 90х, меня интересуют материалы после 2010 года. Возможно есть какие-то новые вариации X-tree или MVP-tree, о которых я ещё не знаю ... Я не понимаю почему, по вашему, иерархические структуры чужды реляционной алгебре, но вот понятие списка соседей и его использование как реляционной проекции для меня просто очевидно - это очень простые вещи. В любом случае, Спасибо.

[uvelichitel]

"после 2010 года" RDF N-Triples N-Quads SPARQL ?

[Юрий Ярош]

uvelichitel: это не с той оперы, интересуют именно структуры данных а не спецификации разметки.

Answer 2

[Юрий Ярош]

Из интересных и перспективных структур пока откопал Fusion-tree и AF-heap.
Было бы неплохо оформить cache oblivious версии.

Comments

[Юрий Ярош]

Пока это всё что откопал.
Думаю ничего круче сейчас не найду.
Пошёл писать статью на хабр.

[Сергей]

Выложите ссылку сюда, плз.

[uvelichitel]

Про дерево Фенвика читали?(мне раньше не попадалось, а сейчас выплыло) и еще sparse set array research.swtch.com/sparse

[Юрий Ярош]

uvelichitel: про sparse set array слышал от Russ'a Cox'a, дерево Фенвика используется для ускорения некоторых операций Y-fast trie структуры.

[uvelichitel]

ну да, забавно в дереве Фенвика, что на вид оно не очень дерево. Впрочем heap то же легко в последовательность сериализуется. Напишите статью о сериализации сложных иерархий)) (или скажите не буду - этот аспект не интересен, тогда может быть я напишу)

[Юрий Ярош]

uvelichitel: в некоторых случаях всё довольно сложно, так как разные структуры имеют разный amplification плюс по разному утилизируется I/O, особенно весело с оперативкой и SSD'шками. Можете написать статью об lsm-tree - это наиболее распространённая структура для хранения иерархической информации, используется в sqlite, cassandra, mongo, leveldb. Возможно найдёте что-то получше или предложите свой интересный вариант. Советую почитать бумагу токутека insideanalysis.com/wp-content/uploads/2014/08/Toku... по этому поводу.