Танцующие деревья

Можно ли эту схему понять ещё на один уровень - чтобы в кеше процессора деревья были сбалансированы, а в регистрах - нет, как это сделать?

как ты деревья в регистры запихнуть собрался?

В теории можно, а вот хватит ли для этого объёма кеша процессора - большой вопрос. Надо конкретную информацию по этому дереву, а не пустословие, которое сейчас в википедии написано.

Очевидно же:

movt (%rdi), %tree1
balt %tree1
movt %tree1, (%rsi)

как эти деревья работают.

«распаковываются»

Надо конкретную информацию по этому дереву

Это Рейзер придумал для своей файловой системы, но не знаю где читать описание в словесном виде, а не в виде исходников модуля...

Мне непонятно как эти деревья работают.

https://github.com/intelfx/linux/blob/reiser4-3.15/fs/reiser4/tree.c
https://github.com/intelfx/linux/blob/reiser4-3.15/fs/reiser4/flush.c

не знаю где читать описание в словесном виде

Его нет.

ОУ Е БЭЙБИ ДЭНС ВИЗ МИ ОЛЛ ЗЭ НАЙТ, КОЗ АЙ ЭМ ФАКН ДЭНСИНГ ТРИИ!!! ОУ Е!!

I wonder how

I wonder why

Yesterday you told me 'bout the blue blue sky

And all that I can see is just a dancing tree

is just a dancing tree

is just a dancing B+ tree

Пунктационные фейерверки, кавалькады смыслов, танцующие деревья, тонущие двери, убегающие окна

я почитал это, ничего не понял, но теперь мне кажется, что надо читать про структуры с Non-Blocking операциями, типа такого -
http://mcg.cs.tau.ac.il/papers/opodis2012-rangeq.pdf
range queries in Non-blocking k-ary trees

ничего не понял

Ожидаемый эффект достигнут :)

Собственно, это было к тому, что доков по dancing trees сейчас нет от слова «совсем», и когда они появятся — неизвестно.

Единственный активный мейнтейнер reiser4 сейчас Эдуард Шишкин, и у него, судя по всему, хронически не хватает времени. Я изредка присылаю туда патчи, но о том, как работают внутренние слои reiser4, не имею ни малейшего понятия.