Дерево с большим количеством элементов данных и потомков называется многопутовым деревом.
Деревья 2-3-4
Сбалансированные деревья, которые ведут себя также как красно-черные деревья, обладают чуть меньшей эффективностью, но более простые в реализации. У 2-3-4 деревьев каждый узел может иметь до 4 потомков 3 элементов данных.
- Узел с одним элементов данных всегда имеет двух потомков.
- Узел с двумя трех потомков
- Узел с тремя четырех потомков.
Новые элементы вставляются в листья, находящиеся в нижнем ряду дерева. Если в процессе вставки полные узлы не обнаружены ( полный узел - это узел с 3 элементами.), то вставка осуществляется легко. Если при вставке на пути вниз к позиции вставки встречается заполненный узел, осуществляется разбиение полного узла.
Эффективность 2-3-4 деревьев
В деревьях 2-3-4 узел может иметь до 4 потомков. Если бы все узлы дерева были б заполнены, то поиск бы занимал log от N по основанию 4, или log2(N+1/2). Т.е высота дерева 2-3-4 может быть в два раза меньше чем высота обычного двоичного дерева. С другой стороны каждый узел содержит больше элементов, т.к для проверки элементов используются линейный поиск. Получается сложность поиска - M*log4N, где M - это количество элементов в узле. Но на самом деле все это ерунда и сложность алгоритма поиска примерно такая же как и у красно-черных деревьев O(logN)
2-3 деревья
Такая же херня, но дерево может иметь до 3 потомков и до 2 элементов в узле. Идеологически все то же самое, при вставки, если встретиться полный узел происходит разбиение.
B дерево
B-дерево удобен при нахождении данных во внешней памяти, например на жестком диске.
B-деревья по умолчанию используются как индексы для .
postgresSQL Хотя он поддерживает и другие индексы, например хеширование
Основная идея в том, что чтение с диска осуществляется блоками. Например, если у нас есть таблица с миллионом записью, где каждая запись весит N кб, то чтение производится сразу многих записью, размером N*16, например. Разумеется количество одновременно считываемых записей зависит от размера записи, от размера считываемого блока и т.д.
B-деревья, это те же 2-3-4 деревья, только вместо максимального количество в 4 потомка, а сколько угодно потомков, например 16. Т.е каждое обращение к диске считывает 16 записей из базы в память. Каждый блок данных содержит ссылку на узлы, находящиеся в других блоках памяти
Большое количество потомков необходимо, чтобы уменьшить количество обращений к диску, до log16(N). Чем больше основание этого логарифма, тем больше записей из базы считывается. Ну а дальше уже в памяти осуществляется линейный поиск по считанным записям. Если чтение из оперативной памяти осуществляется абсолютно бесплатно (т.е именно обращение к конкретному элементу), то чтение с диска - это дорогостоящая операция, и надо эти чтения минимизировать
