#btree

🏳️‍🌈🤘 Blain Smithblainsmith@snac.rblgk.sh
2025-06-06
I've been messing around with trees in Hare lately so I started with a standard BTree. It is not fully tested yet, but I will release it when I feel it is ready.

I will probably move to a B+Tree after that.

#DataStructures #BTree #SystemsProgramming #HareLang
N-gated Hacker Newsngate
2025-05-30

OrioleDB's Indexes: because who doesn't love yet another revolutionary feature that promises to fix problems nobody knew existed? 🤔🎉 Let's all pretend this complex jargon will change our lives while we secretly Google "Btree" like it's a trendy new diet. 🍽️📚
orioledb.com/blog/orioledb-bri

2025-05-22

Правильный порядок колонок в B-tree индексах PostgreSQL или правило ESR

Когда в проекте используется составной B-tree индекс, важно не просто "создать индекс", а сделать это правильно — иначе запросы могут не только не ускориться, но и начать работать медленнее. Возникает логичный вопрос: как выбрать порядок колонок, чтобы индекс действительно работал эффективно? Брутфорсом? По интуиции? По селективности? В этой статье я расскажу, как подходить к построению составных индексов в PostgreSQL, на что реально влияет порядок колонок. Также разберём простое правило ESR, которое помогает упростить выбор и получать стабильный прирост производительности на всех стендах.

habr.com/ru/articles/911688/

#postgresql #Btree #составной_индекс #многоколонковый_индекс #ESR_правило #оптимизация_запросов #селективность #план_выполнения #explain_analyze #индексный_скан

2025-02-20

B-Tree — сбалансированный куст поиска

В реляционных СУБД есть дефолтный тип индекса — B‑Tree: Tree в названии однозначно указывает на дерево, ну а В это, наверно, Binary? Или Balanced? Или Balanced Binary? Почему‑то долгое время я полагал, что это Balanced Binary, и эта версия даже «работала». На деле всё куда интереснее, предлагаю проследовать под кат, чтобы посмотреть на этот на самом деле скорее низкорослый куст и сравнить его с Red‑Black Tree на Java. Точно куст?

habr.com/ru/articles/884232/

#java #btree #tree #дерево

2025-02-13

Хеш-индексы в PostgreSQL: быстрый поиск или скрытые проблемы?

Хеш-индексы в PostgreSQL - мощный, но недооценённый инструмент. Когда они быстрее B-Tree, а когда наоборот? Простое объяснение, тесты и ключевые нюансы, которые помогут ускорить запросы...

habr.com/ru/articles/882106/

#базы_данных #sql #оптимизация_запросов #индексы #btree #hash #производительность #BTree_vs_Hash #разработка #dba

2024-10-22

[Перевод] Насколько быстры B-деревья по сравнению с хэш-таблицами?

Во многих «скриптовых» языках для стандартных ассоциативных структур данных используется хэш-таблица (hashmap) (объекты Javascript, словари Python и так далее). Хэш-таблицы обладают множеством раздражающих свойств: Уязвимость к hash flooding . В случае защиты от hash flooding случайными seed порядок итераций становится недетерминированным, что мешает при тестировании снэпшотов, создании воспроизводимых сборок и так далее. При вставке может требоваться рехэширование, что в наихудших случаях создаёт для больших хэш-таблиц ужасные задержки. Многократное увеличение больших распределений памяти без фрагментации сложно реализовать в целевых платформах wasm, потому что трюки с виртуальной памятью недоступны, а для страниц невозможно выполнить unmapping. Векторные команды в wasm ограничены, а команды AES отсутствуют. Это делает многие хэш-функции ещё более медленными. Упорядоченные структуры данных наподобие B-деревьев не имеют этих недостатков. Обычно они медленнее хэш-таблиц, но меня удивило, насколько разнятся ожидания людей относительно их скорости.

habr.com/ru/articles/849654/

#bдерево #хэштаблицы #btree #hashmap #поисковые_алгоритмы #бенчмарки

2024-09-15

Linked is a neat article explaining a lot about b-trees. Especially notable are the excellent visualization and animations which gave me a new way to understand these incredibly important data structures.salas.com/2024/09/14/b-trees-a #performance #indexes #btree #databasedesign #datavisualization #datastructure

Andreas Scherbaumascherbaum
2024-08-07
2024-02-02

#PGSession16 : mercredi prochain, Frédéric Yhuel nous mettra en garde contre les pièges de l'interprétation des plans d'exécution. Comme les précédentes, sa #conférence sera retransmise en direct sur dali.bo/2023_site_pgsessions

#DBA #SGBD #opensource #logicielsLibres #index #btree

2023-12-26

[Перевод] Почему B-деревья быстрые?

B-дерево — это структура, помогающая выполнять поиск в больших объёмах данных. Она была изобретена более сорока лет назад, однако по-прежнему используется в большинстве современных баз данных. Хотя существуют и более новые структуры индексов, например, LSM-деревья, B-дерево пока никто не победил в обработке большинства запросов баз данных. После прочтения этого поста вы будете знать, как B-дерево упорядочивает данные и выполняет поисковые запросы.

habr.com/ru/articles/783012/

#btree #bдерево #индексация #базы_данных #алгоритмы_на_графах #двоичное_дерево_поиска

Ambassador Tablicekstrizhechenko@lor.sh
2023-07-25

#федичитальня #postgresql #postgresql15

Сортировка по индексу.

#Btree #индексы можно и для сортировки за O(n) использовать без буферизации всех строк где-либо. Но с неопределёнными значениями и порядком сортировки есть нюанс - положение их в индексе задаётся при создании и, если запрашиваемое положение отличается, то индекс не может быть использован.

Вообще странно, что не воткнули костыль для простейших случаев, если nulls не там, просто читаем индекс с другого конца, до тех пор, пока не наткнёмся на не #null, после чего начнём читать индекс так, как изначально и планировалось, до тех пор, пока не на кнёмся на null, который послужит нам эдаким EOF. Сложность чтения бы сохранилась линейной, всего пару переменных и ифников для стейт-контрола добавить. Не думаю, что это был бы значимый оверхед.

Florian Lawsflaws@bawue.social
2022-11-25

A blog article with an overview of modern variants of B-Tree data structures.

erthalion.info/2020/11/28/evol

#btree

Ivan Sagalaev :flag_wbw:isagalaev
2019-12-10

A good explanation of trade-offs between hashes and b-trees: evanjones.ca/ordered-vs-unorde

Written in simple language, well-scoped and short. It's destined to become a piece people link to all the time.

Client Info

Server: https://mastodon.social
Version: 2025.04
Repository: https://github.com/cyevgeniy/lmst