Indexação B-Tree
Deslize para mostrar o menu
Um índice B-tree é uma estrutura de dados em árvore balanceada comumente utilizada em bancos de dados para organizar e buscar grandes volumes de dados de forma eficiente.
B-trees são muito semelhantes às árvores binárias de busca (BST), mas os nós em uma B-tree podem ter mais de dois filhos.
A B-tree armazena chaves em ordem classificada dentro dos nós, permitindo a recuperação rápida de dados por meio da travessia hierárquica do nó raiz até os nós folha. A indexação B-tree é adequada para consultas por intervalo e buscas por igualdade, tornando-se uma escolha popular para otimizar o desempenho de bancos de dados.
Uma consulta por intervalo é uma operação de banco de dados que recupera dados dentro de um intervalo especificado de valores para um determinado atributo ou coluna. Permite recuperar registros que se enquadram em um intervalo definido, como valores entre duas datas ou dentro de um intervalo numérico. Os seguintes operadores são usados em buscas por intervalo: >, <, >=, <=.
Uma busca por igualdade é uma operação de banco de dados que recupera dados com base em uma correspondência exata de um valor especificado para um determinado atributo ou coluna. Permite encontrar registros que correspondam exatamente a um critério definido, como encontrar todos os clientes com um endereço de e-mail específico ou um determinado ID de usuário. Essas consultas incluem os operadores = e <>.
Como funciona?
O índice B-tree organiza os dados de forma hierárquica, com cada nó contendo um número fixo de chaves e ponteiros para nós filhos.
As B-trees mantêm o balanceamento garantindo que todos os nós folha estejam no mesmo nível, o que otimiza as operações de busca.
Ao buscar uma chave específica, o algoritmo B-tree percorre a árvore do nó raiz até os nós folha, utilizando busca binária para localizar de forma eficiente a chave desejada.
Busca por índice envolve percorrer a árvore até alcançar os nós folha, seguir a cadeia de nós folha para encontrar os registros correspondentes e recuperar os dados reais do disco.
Na figura, a busca pela chave 302 é ilustrada:
-
Uma estrutura de árvore de busca é um tipo de árvore onde cada nó possui dois ponteiros: o ponteiro à esquerda aponta para nós filhos com valores menores que o nó pai, e o ponteiro à direita aponta para nós filhos com valores maiores que o nó pai;
-
Em uma B-tree, o nó raiz pode conter múltiplos valores de índice. Por exemplo, se a raiz contém três valores distintos, ela terá três ponteiros, cada um indicando o intervalo de valores entre essas chaves;
-
Para buscar uma chave, como
302, a busca começa no nó raiz e segue os ponteiros apropriados até os nós folha. A busca é concluída após percorrer três blocos da árvore, conforme destacado em vermelho no diagrama; -
Para buscar um intervalo de valores a partir de
302, é possível utilizar os ponteiros horizontais entre os nós folha. Por exemplo, recuperar valores de302a502é feito seguindo os nós folha sequencialmente.
A chave utilizada para busca em um índice B-tree vem dos valores armazenados nas colunas indexadas da tabela do banco de dados. Por exemplo, se o índice está em uma coluna como "client_id", a chave de busca será o valor real de "client_id". Cada valor numérico único na coluna indexada serve como uma chave no índice B-tree, facilitando a localização e recuperação das linhas correspondentes na tabela do banco de dados.
Vantagens e desvantagens
Diferente da estrutura de dados padrão Binary Search Tree, os nós de B-tree podem acomodar mais de 2 filhos. O número máximo padrão de filhos por nó geralmente é definido como 16.
Implementação de índice
Para criar um índice B-tree em uma coluna no PostgreSQL, utilize o seguinte comando SQL:
CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);
Como o índice B-tree é o índice padrão em SQL, também podemos usar a seguinte instrução para criá-lo:
CREATE INDEX index_name ON table_name(column_name1, column_name2,..);
Em SQL, ao criar uma tabela com uma restrição de chave primária, a maioria dos sistemas de gerenciamento de banco de dados cria automaticamente um índice na(s) coluna(s) especificada(s) na chave primária. Esse índice auxilia na aplicação da restrição de unicidade da chave primária e também melhora o desempenho de consultas que envolvem buscas ou junções baseadas na(s) coluna(s) da chave primária.
Obrigado pelo seu feedback!
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
Indexação B-Tree
Um índice B-tree é uma estrutura de dados em árvore balanceada comumente utilizada em bancos de dados para organizar e buscar grandes volumes de dados de forma eficiente.
B-trees são muito semelhantes às árvores binárias de busca (BST), mas os nós em uma B-tree podem ter mais de dois filhos.
A B-tree armazena chaves em ordem classificada dentro dos nós, permitindo a recuperação rápida de dados por meio da travessia hierárquica do nó raiz até os nós folha. A indexação B-tree é adequada para consultas por intervalo e buscas por igualdade, tornando-se uma escolha popular para otimizar o desempenho de bancos de dados.
Uma consulta por intervalo é uma operação de banco de dados que recupera dados dentro de um intervalo especificado de valores para um determinado atributo ou coluna. Permite recuperar registros que se enquadram em um intervalo definido, como valores entre duas datas ou dentro de um intervalo numérico. Os seguintes operadores são usados em buscas por intervalo: >, <, >=, <=.
Uma busca por igualdade é uma operação de banco de dados que recupera dados com base em uma correspondência exata de um valor especificado para um determinado atributo ou coluna. Permite encontrar registros que correspondam exatamente a um critério definido, como encontrar todos os clientes com um endereço de e-mail específico ou um determinado ID de usuário. Essas consultas incluem os operadores = e <>.
Como funciona?
O índice B-tree organiza os dados de forma hierárquica, com cada nó contendo um número fixo de chaves e ponteiros para nós filhos.
As B-trees mantêm o balanceamento garantindo que todos os nós folha estejam no mesmo nível, o que otimiza as operações de busca.
Ao buscar uma chave específica, o algoritmo B-tree percorre a árvore do nó raiz até os nós folha, utilizando busca binária para localizar de forma eficiente a chave desejada.
Busca por índice envolve percorrer a árvore até alcançar os nós folha, seguir a cadeia de nós folha para encontrar os registros correspondentes e recuperar os dados reais do disco.
Na figura, a busca pela chave 302 é ilustrada:
-
Uma estrutura de árvore de busca é um tipo de árvore onde cada nó possui dois ponteiros: o ponteiro à esquerda aponta para nós filhos com valores menores que o nó pai, e o ponteiro à direita aponta para nós filhos com valores maiores que o nó pai;
-
Em uma B-tree, o nó raiz pode conter múltiplos valores de índice. Por exemplo, se a raiz contém três valores distintos, ela terá três ponteiros, cada um indicando o intervalo de valores entre essas chaves;
-
Para buscar uma chave, como
302, a busca começa no nó raiz e segue os ponteiros apropriados até os nós folha. A busca é concluída após percorrer três blocos da árvore, conforme destacado em vermelho no diagrama; -
Para buscar um intervalo de valores a partir de
302, é possível utilizar os ponteiros horizontais entre os nós folha. Por exemplo, recuperar valores de302a502é feito seguindo os nós folha sequencialmente.
A chave utilizada para busca em um índice B-tree vem dos valores armazenados nas colunas indexadas da tabela do banco de dados. Por exemplo, se o índice está em uma coluna como "client_id", a chave de busca será o valor real de "client_id". Cada valor numérico único na coluna indexada serve como uma chave no índice B-tree, facilitando a localização e recuperação das linhas correspondentes na tabela do banco de dados.
Vantagens e desvantagens
Diferente da estrutura de dados padrão Binary Search Tree, os nós de B-tree podem acomodar mais de 2 filhos. O número máximo padrão de filhos por nó geralmente é definido como 16.
Implementação de índice
Para criar um índice B-tree em uma coluna no PostgreSQL, utilize o seguinte comando SQL:
CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);
Como o índice B-tree é o índice padrão em SQL, também podemos usar a seguinte instrução para criá-lo:
CREATE INDEX index_name ON table_name(column_name1, column_name2,..);
Em SQL, ao criar uma tabela com uma restrição de chave primária, a maioria dos sistemas de gerenciamento de banco de dados cria automaticamente um índice na(s) coluna(s) especificada(s) na chave primária. Esse índice auxilia na aplicação da restrição de unicidade da chave primária e também melhora o desempenho de consultas que envolvem buscas ou junções baseadas na(s) coluna(s) da chave primária.
Obrigado pelo seu feedback!
