высоко в горах и на высоте 10 км где летают самолеты очень холодно (несмотря на разряженную атмосферу)

В википедии сказано что как правило фиксированное:

Б+-деревья используются для хранения данных на жёстких дисках.

В википедии сказано что как правило фиксированное:

Плюс у DOUGLAS COMER так же чётко сказано что ключей в узле 2d.

In general, each node in a B-tree of order d contains at most 2d keys and 2d + 1 pointers, as shown in Figure 4.

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

Ключи там есть К примеру такие ключи как i_size и i_mtime

В ext не используется битовая карта(сегментированный массив блоков)

У B(+)-деревьев количество дочерних узлов может варьироваться. У карты файловых блоков количество элементов в каждом узле (кроме последнего "листа") фиксировано.

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range.

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

Узлы B(+)-дерева содержат как ссылки на дочерние узлы/листья, так и значения ключей. Карта файловых блоков содержит только ссылки, никаких ключей в ней нет.

struct ext2_inode {
__u16 i_mode; /* Тип файла и права доступа (см.ниже) */
__u16 i_uid; /* UserID */
__u32 i_size; /* Размер в байтах */
__u32 i_atime; /* POSIX время последнего обращения к файлу */
__u32 i_ctime; /* POSIX время создания */
__u32 i_mtime; /* POSIX время последней модификации */
__u32 i_dtime; /* POSIX время удаления */
__u16 i_gid; /* GroupID */
__u16 i_links_count; /* Кол-во ссылок на дескриптор */
__u32 i_blocks; /* Кол-во секторов (не блоки!) */
__u32 i_flags; /* Флаг (см.ниже) */
union {
struct {
__u32 l_i_reserved1; /* Зарезервировано */
} linux1;
struct {
__u32 h_i_translator; /* ??? */
} hurd1;
struct {
__u32 m_i_reserved1; /* Зарезервировано */
} masix1;
} osd1;
__u32 i_block[EXT2_N_BLOCKS];/* Указатели на блок */
__u32 i_generation; /* Версия файла (для NFS) */
__u32 i_file_acl; /* Доп. аттрибуты файла */
__u32 i_dir_acl; /* Доп. аттрибуты директории */
__u32 i_faddr; /* Адрес фрагмента */
union {
struct {
__u8 l_i_frag; /* Номер фрагмента */
__u8 l_i_fsize; /* Размер фрагмента */
__u16 i_pad1; /* Зарезервировано */
__u16 l_i_uid_high; /* 16 старших битов UserID */
__u16 l_i_gid_high; /* 16 старших битов GroupID */
__u32 l_i_reserved2; /* Зарезервировано */
} linux2; /* LINUX */
struct {
__u8 h_i_frag; /* Номер фрагмента */
__u8 h_i_fsize; /* Размер фрагмента */
__u16 h_i_mode_high; /* 16 старших битов T&P */
__u16 h_i_uid_high; /* 16 старших битов UserID */
__u16 h_i_gid_high; /* 16 старших битов GroupID */
__u32 h_i_author; /* UserID или автор */
} hurd2; /* GNU HURD */
struct {
__u8 m_i_frag; /* Номер фрагмента */
__u8 m_i_fsize; /* Размер фрагмента */
__u16 m_pad1; /* Зарезервировано */
__u32 m_i_reserved2[2]; /* Зарезервировано */
} masix2; /* MASIX */
} osd2; /* Специфичные значения */
};

B(+)-дерево - это дерево поиска. Карта файловых блоков - это, в общем-то, и не дерево, это сегментированный массив.

2. B(+)-деревья позволяют вставку и удаления узла/листа, при этом затрагивается максимум log(n) узлов. Чтобы вставить или удалить узел в карту файловых блоков, нужно перетряхнуть все последующие узлы (в худшем случае - вообще все).

Зато конечно у нас есть полтора тролля, Киля ещё не забаненный в очередной раз Кролег. Супергеройская команда в общем, но может и что получится, я в теме если что ;)

В космосе ещё холоднее, но аппараты перегреваются. Нет атмосферы, нет конвективного теплообмена.

Поэтому логичней, взять за основу сразу частоту CPU 1..3 GHz, и его счётчик тактов TSC. Бонусом, не помешала-бы и сериализация на входе/выходе через инструкцию LFENCE.. т.е. учитывать спекулятивное выполнение кода процессором.

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.

Скрытый текст

Задачу я непременно тут запощу в отдельной теме, только сейчас не могу, статья ещё не вышла.
Может кто помнит, 5 лет назад я тут на сорцах мучалась с алгоритмом размещения абсолютного 1-центра неориентированного графа, даже тема старая есть.
Вот эту задачу я сделала, алгоритм простой, прямыми вычислениями в двойном цикле за квадратичное время все эквивалентные центры находятся для одного ребра.
Эту задачу и некоторые обобщения.

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.
Пока я этого не сделала, у Хакими алгоритм быстрее.
Вначале, конечно, сама попробую сделать, всё равно летом никуда не поедешь.

создай отдельную тему и там разбирайся

на нём одном весь раздел держится

Скрытый текст

Хакими за счёт использования 2-3 деревьев понизил сложность своего алгоритма с O(n^3) до O(nlogn).
Мне даже смотреть противно на эти 2-3 деревья.
У меня честные двумерные массивы и двойной цикл крутится.
Чтобы догнать Хакими, мне нужно всего-то с O(n^2) понизить до O(nlogn). Вот только не пойму как.
Кнута что ли почитать...

Вообщем цель, сидеть на 8-битах с русским/казахским текстом возможна ли?

класса обвертки?