Árvores B e B+. Estas são estruturas de dados fundamentais, muito importantes e utilizadas amplamente nos mecanismos de indexação, nos índices dos nossos bancos de dados. A árvore B, inventada por Bayer e McCrick enquanto trabalhavam na Boeing, com o propósito de gerenciar com eficiência páginas de índice para grandes arquivos de acesso aleatório. Adequada para sistemas de armazenamento que leem e escrevem blocos de dados grandes como banco de dados ou sistemas de arquivos. Então aqui a gente já percebe que essa estrutura de dado, que é a árvore B, tem como propósito a otimização da forma de acesso em grandes massas de dados. Aqui eu quero destacar, inclusive, os dois casos de uso pensados, os bancos de dados, que é onde nós estamos nos aprofundando, porém nós vamos encontrar a árvore B também em sistemas de arquivo. Já vamos olhar juntos essa estrutura de exemplo que eu trouxe aqui, então nós temos uma árvore B, onde esse primeiro nó que está mais para cima, que tem as chaves número 7 e 16, é o nó raiz ou nó pai e nós já sabemos que registros anteriores a chave 7, ao número 7, estarão à esquerda, no próximo nó, que é o nó à esquerda, que contém 1, 2, 5 e 6. Também pela lógica aqui da árvore B, nós vamos perceber que elementos que estão acima do número 7 e abaixo do 16, vão estar na outra folha, ou no outro nó, entre o 7 e o 16. Então, nós vamos ver o nó intermediário com as chaves número 9 e número 12. E assim, na mesma lógica, tudo aquilo que for maior do que 16, estará no terceiro nó à direita, onde nós vamos encontrar este nó, também chamado de nó folha, o nó que está mais abaixo, com os números 18 e 21. Então, por enquanto, vamos prestar bastante atenção neste mecanismo fundamental de organização das informações com base nessas chaves e a distribuição entre os nós destes valores. Aqui nós vamos nos aprofundar e perceber que a árvore B, na verdade, o B aqui vem para balanced, ou balanceada, ou com autoequilíbrio. Então, a ideia é preservar a ordenação dos dados. Então, percebam que neste exemplo que eu comentei com vocês, os números estão ordenados entre os três nós, inclusive nas chaves do nó raiz, do nó pai. do nó pai, e a ideia aqui, então, de ter essa ordenação e permitir pesquisas, acesso sequencial, inserções e exclusões em tempo logarítmico. Deixa eu falar de uma maneira mais direta. Tempo logarítmico significa que não importa o tamanho da base de dados, o tempo para uma pesquisa, para um acesso, para uma inserção, para uma exclusão, será o mesmo. Lembra daquele grande objetivo que é não navegar por todos os registros. Se a gente tivesse que navegar registro a registro, imagina que numa grande base de dados, para você fazer uma inserção ou uma leitura, essa operação demoraria muito tempo. Então, a árvore B é uma estrutura de dados que tem este comportamento, tempo logarítmico. Profundando um pouquinho mais sobre este conceito, a razão entre número de operações e o tamanho da entrada diminui e tende a zero quando N aumenta. Ou seja, quanto mais registros na nossa base de dados, o tempo diminui e vai tender a zero. Então, quanto mais crescer essa base de dados, para você conseguir acessar um registro via este índice, o tempo vai ser praticamente o mesmo. Então, um algoritmo que deve acessar todos os elementos de sua entrada, ou seja, de sua base de dados, nunca é tempo logarítmico, pois o tempo para ler uma entrada de tamanho N é da ordem de N. Ou seja, se tiver que ler todos os registros, quanto mais registros forem necessários serem lidos, maior o tempo. Então, a característica especial do tempo de acesso de uma árvore B é o tempo logarítmico. Um pouco mais agora sobre estrutura da árvore B. Todas as folhas estão no mesmo nível, o que vai tornar esta árvore balanceada. A raiz, que é aquele nó lá em cima, ou o nó pai, tem pelo menos dois filhos. Todos os nós internos, exceto a raiz, vão possuir um número de filhos que vai variar de D, que é o mínimo grau mínimo desta árvore, a 2D. Um nó não folha com K filhos contém K menos 1 chaves. Ou seja, se um nó tiver três filhos, ou seja, o K igual a 3, este nó vai conter duas chaves, que é o K menos 1, para segmentar os dados em três partes correspondentes a cada nó filho. Exatamente como a gente viu nesse primeiro exemplo, no começo aqui da nossa aula. Pouco mais desta estrutura de árvore B. Então, uma excelente estrutura de dados para armazenar dados que não vão caber em memória RAM, na memória principal, porque o design aqui minimiza o número de acessos ao disco. Esta árvore é balanceada, todos os nós folha na mesma profundidade e os tempos de pesquisa, consequentemente, vão permanecer consistentes e previsíveis. Então, aqui vamos relembrar que a organização, eu tenho o pai com a chave 30, o que está à esquerda vai ser menor do que 30 e a direita maior. Aí nós vamos ter um nível intermediário com os nós do meio, 8 e 90. O que está à esquerda do 8 é menor do que 8, vai aparecer um filho com o número 1, e o outro filho à direita, maior do que 8, porém menor do que 30, o número 20. E o mesmo raciocínio nós vamos observar ali em relação ao 90. À esquerda, a gente tem tudo que é menor do que 90, porém maior do que 30, e à direita nós vamos ter tudo aquilo que é maior do que 90, 99 e 150. E como tudo na vida evolui, a árvore B evoluiu e nós temos a árvore B+, que é uma variante da nossa árvore B. A árvore B+, amplamente utilizada em banco de dados para os nossos índices, principalmente bancos relacionais. Diferenças, características da árvore B+, os dados, os ponteiros dos dados, ou seja, aquele apontamento para onde está a informação, são armazenados apenas nos nós. Folha não vai estar no nó pai. Os nós internos terão apenas chaves e ponteiros para outros nós. Então, muito mais chaves poderão ser armazenadas nos nós internos. Isso vai reduzir a altura da árvore. Uma árvore de altura mais baixa diminui o número de acesso ao disco para executar as operações de leitura. Todos os nós folha estarão numa estrutura que é o Linked List, ou lista vinculada. Então, consultas de intervalo, eu quero entre o número 1 e o número 10. Serão consultas muito eficientes. Então, é acessado o primeiro nó desse intervalo e o Linked List, como tem o apontamento, como é uma lista que aponta para a cadeia seguinte, vai simplesmente seguir essa lista até pegar o valor restante. Cada chave na árvore do E mais vai aparecer duas vezes. Uma vez nos nós internos e uma vez no nó folha. Então, nos nós internos, essa chave vai atuar como aquela divisão, aquela segregação, para você optar numa leitura que vai para o lado direito ou para o lado esquerdo da nossa árvore. Ou seja, decidir qual subárvore será acessada para encontrar o valor que nós estamos buscando. Aqui, ainda a subárvore B+. Então, são particularmente adequadas para sistemas com grandes quantidades de dados, que não cabem em memória RAM. Como os dados só podem ser acessados a partir dos nós folha, cada pesquisa requer um percurso de caminho da raiz até uma folha. Todas as operações de acesso aos dados vão levar um tempo consistente também.