| вещь, о которой никто не пишет |
[Oct. 2nd, 2019|07:08 am] |
на самом деле самое сложное в реализации b+ — это менеджмент свободных блоков (и вообще свободного места). даже твой кот расскажет тебе, как написать добавление и удаление ключей, но никто не пишет материалов по разным стратегиям управления свободными блоками.
проблема в том, что управлять надо как минимум двумя видами «дырок»: целыми блоками, и частями в блоке. потому что ключи большого размера и данные хранятся отдельно. если на каждый большой ключ или кусочек данных больше ~60 байт выделять по целому блоку, это будет ужас. поэтому блоки с данными надо менеджить отдельно, и выделять там меньшими сегментами.
при этом списки свободного места должны быть компактные (они тоже лежат на диске в блоках же), обеспечивать быстрый поиск, и — что очень важно — быструю вставку со слиянием (чтобы последовательное пустое место можно было объединять обратно в блоки). не забываем также, что у нас на самом деле два типа свободных блоков: «совсем свободные» и «свободные только после закрытия вон того списка читающих транзакций». так что в идеале нужна ещё и быстрая операция слияния списков.
возможно, стоит использовать для этого то же самое b+tree. но не очень понятно тогда, по какому критерию сортировать блоки. с одной стороны, для быстрого слияния их надо сортировать по файловой позиции. а с другой — нам нужны и запросы по подходящему размеру. совсем в идеале — блоки, только что освобождённые транзакцией записи, надо бы по следующему запросу выделять первыми, потому что есть большой шанс, что они уже в дисковом кэше. но это не обязательно, и в принципе, можно менеджить отдельно.
если у кого-то есть по этому поводу интересные идеи (или статьи) — вэлкам. глупость в комментариях к этому псто демонстрировать не надо, пожалуйста: есть вон пост про грету, поидиотничать можно там.
p.s.: xfs, похоже, не парится, и держит два дерева, сортированых как по смещениям, так и по размерам. понятно, что это тоже вариант, но он мне совсем не нравится. |
|
|