Árvores B

o Olá hoje nós vamos falar sobre as árvores B que foram inventados em 1970 por Bayern e McQueen você pode pensar nas árvores ver como se fossem uma generalização das Árvores dois três só que ao invés de ter no máximo duas Chaves pornô nas árvores bem nós podemos ter uma quantidade muito maior de Chaves por não as árvores B elas foram inventadas para resolver o problema de quando a nossa estrutura de dados né ela não cabe inteiramente namora principal você gente tem uma estrutura de chave-valor né vou ficar da chave que corresponde a um determinado

valor Só que essa estrutura ela não tá bem melhor que sol então é necessário que essa estrutura ela possa ser realizada para memória secundária E no caso quando a memória secundária gente tá falando por exemplo de disco rígido ou de HD SSD por exemplo um dia ou tantas outras formas de armazenamento secundário que existe então embora você possa implementar uma árvore B para armazenar não é uma uma estrutura chave e valor aí memória principal ela foi pensado primeiramente nos casos onde a estrutura não cabe totalmente em memória principal Então as árvores belas são utilizadas como

uma estrutura auxiliar para implementar várias aplicações de complexos como o banco de dados por exemplo sistema de arquivos em sistemas operacionais modernos Se precisarem de uma generalização de uma estrutura de dados para armazenamento de pares chave-valor em árvore existem muitas implementações possíveis as árvores B é e nós vamos estudar duas delas bebê mas profissional e as árvores demais são RN na verdade na Essência e continua sendo o maior bebê mas com algumas modificações a existem muitas outras variações que foram criados de acordo com as aplicações específicas que elas preferiam resolver nem tanto a ideia básica

de toda a série B é essa que eu vou apresentar para vocês hoje nessa possível estrutura de árvore B que eu vou discutir com vocês os valores ficam juntamente com as chaves então vocês podem ver por exemplo nesse exemplo o que que eu não estritamente coloquei os valores são Associados em cadastrar mas é importante que eu tô dizendo pra vocês aqui é que cada chave já e o seu valor diretamente na estrutura professores isso não é o que a gente já vem fazendo desde que a gente começou a estudar outras outras Artes sim tá mas

o que a gente vai ver na próxima aula que nada no caso das Árvores vem mais por exemplo todos os dados correspondentes as chaves ficam nas folhas e nos intermediários das Artes São apenas índices e não contém os dados correspondem a é como eu disse para vocês a ideia da árvore b a ideia que ela foi pensado Originalmente é que ela deve funcionar sem ter que ficar totalmente carregado em memória Então na verdade a ideia é que você faça as buscas nessa árvore abrindo cada pedaço vai estrutura de forma independente para você não tem que

carregar Pô toda ela se não você não tá resolvendo o problema de novo ter que ficar com a estrutura e não poder na verdade está com a estrutura toda carregada em memória a ideia aqui cabra nova essa árvore que a gente tem aqui presente então a gente vai carregar cada pedaço desses árvore jogo da memória secundária o forma a gente vai precisando tá então foi vez a gente chamar os nossos numa árvore-b de nós a gente vai chamar ele de página é páginas por que a gente faz a distinção porque novamente As páginas você muito

maiores do que um nó comum de uma árvore que normalmente a carregada em memória principal exemplo aqui eu tô fazendo um exemplo de uma árvore de um ordem e onde é igual a quatro a pessoa só porque é bem mais fácil de desenhar nosso com quatro elementos no entanto na prática quando a gente usar a bebê é muito comum que acaba quase não ter milhares de Chaves tá então é bem importante que eu faço essa distinção para vocês que vocês entendam é que esse é um exemplo simplificado Por que seja fácil da gente discutir a

gente vezes seus sonhos vivemos mas a prática então cada página que é o nó da árvore B pode ter então milhares aí de Helena e é uma árvore B Jordan m a ideia que cada zona eu chamei de nós ir embora eu te falo para você assistir o certo chama de página né presidente que cada nova Nossa viver e no máximo e menos um Machados o Iluminismo eles sobretudo Chaves no caso no máximo ele menos um Machados vejo que como eu tenho que quatro espaços aqui a nossa ordem é quatro Tá mas no máximo três

essas chaves voltar voltar ocuparmos um determinado não esse quarto essa parte da posição aqui no nosso exemplo é o eu posso usado temporariamente antes de ter que ser feito a operação de street que leva que a gente já começou algo parecido também estava falando nas árvores 23 onde a gente podia ter temporariamente um nó com três faz logo antes da gente tem que fazer o Sprint bom o que eu entendi essa ideia de ter no máximo e menos uma chave mas no caso mínimo né eu posso ter no máximo emissores do Chaves sim exceto para

isso para lá isso pode ter um mínimo também monta o verdade legal dos verbos bem que elas são perfeitamente O que quer dizer que quando qualquer caminho entre a raiz e as folhas sempre vai ter a mesma quantidade de links e se podem imaginar aqui uma coisa que segue disso não é uma propriedade que sei disso aqui quanto quanto mais chave se a gente puder colocar em cada página mais baixo vai ser essa árvore que ninguém veja serve vai precisar ele ele pessoal uma coisa muito importante que a gente tá pensando em arma bebê é

que é a altura da árvore ela é realmente muito importante de a gente tentar Mandela baixo porque porque a gente tem que lembrar que cada vez que a gente chega a gente tem que abrir uma página na pegadinha está fazendo um acesso de disco ou um acesso remoto né porque tá em outra marca que seja tá em memória principal Esse é o ponto principal e é isso não quer esse acesso em memória secundária isso em muito muito muito mais lento do que a gente acessar coisas que já estão direto na nossa Hum então se a

gente minimiza a quantidade de Oi gente tem que abrir páginas do disco é melhor vai ser o nosso desempenho amassar bebê tá tudo bem Então essa é um primeiro. Aí que a gente tem que pensar uma coisa muito legal dar bebê é que a bebê pode ter literalmente pessoal se a gente vê M = 1000 a gente pode indexar um máximo cinco ou seis níveis dessa árvore que a gente pode interessar cerca de 70 bilhões de registros Então é isso é se você me perguntar eu acho fascinante tá não é uma estruturas extremamente difícil implementar

e mesmo assim gente tem esse poder de indexar bilhões de registros né usando carregando essa estrutura de forma incremental na dinâmica de memória tá então eu acho eu acho realmente e as árvores B são são uma invenção Espetacular da tecnologia 8d e para vocês aqui no nosso exemplo nós temos uma árvore B de ordem quatro então nosso M = 4 aqui isso quer dizer que em cada página a gente vai ter no máximo três três posições ocupados tá eu tive um momento que a gente tem mais do que três posições culpados é necessário que a

gente faça então uma operação de Split e quando a gente for fazer uma ser pedir qualquer forma a gente fala de inserção vamos falar da costura né então a busca pessoal muito simples a busca você carrega a primeira página e daí você vai você verifica a chave que você tá procurando se ela tá antes ou depois de cada uma das chaves que que já estão ocupados aqui na nossa estrutura apresentação de ficar procurando a Chaves e eu sei que senta antes ou depois de panela então pensei que ela tem que estar na sub-árvore esquerda que

ia aqui ó E aí na prática O que é feito na prática se a gente tiver implementando essa árvore em disco a gente vai descarregar essa página e vai carregar seu pai tá e vem para carregar essa parte aqui e daí vai verificar se a chave está procurando é essa aqui ela é uma da chave está por aqui a gente pode fazer essa procura da chave nessa Busca Pela chave que a gente quer encontrar juntamente com avaliação Para ver aonde que a gente vai seguir City não comprar a chave desse nível que a gente vai

procurar achar você né gente vai bater aqui falou pa é menor maior ou glosse é igual eu já achei a chá é porque essa implementação que eu falei para vocês aqui que a gente tá discutindo a os valores tamo junto com as cartas então eu simplesmente a posso pegar o valor que está associado aqui com você E retornar para quem pediu esse valor agora se você tiver procurando o g tá então o G vai antes o GTA antes ou depois de hoje tá depois que quer dizer e nessa página aqui não é para nós subir

árvore que está enraizada nessa página direita aqui depois de tá aí eu pergunto G Vem antes de p = pe é depois de P ou = s ou é depois de bem antes de ver então a gente vai seguir essa super aqui e daí agora vez que a gente chegou não folha e já fazer a mesma verificação é antes de L L é entre l m entre é m entre é melhor é o ou é depois de ó bem era para ser antes de ela às vezes ficou muito chegou no folha tá então a gente

só porque a chave G não está na sala vermelha Então pessoal é ver vamos fazer mais uma música né vou fazer a busca pela letra pela letra ela quer dizer tá então Z antes de ir é igual aí ou depois de aí depois de ir Z a gente e agora essa Paiva é antes de b = p entre o PS é igual a esse ou é depois de esse aqui é depois de essa Ok deve carregar essa página é uma página foi mas a verificação é a mesma tá você vem antes de ter é igual

até ventre trio é igual ou vem depois de um vem depois viu Só que vez que a gente não tem mais nenhuma chave aqui né a gente tá não foi logo Z não está na nossa gripe e tem uma busca pessoal é extremamente simples e muito parecido com a música que a gente fez na árvore dois três só que agora vezes a gente verificar né se a gente tá com um caso com o nódulo nobinario uma alternar you a gente vai simplesmente fazer passar por todos os todas as chaves que a gente tem aqui verificando

se achavam que a gente está procurando bate com uma dessas e se não bater com alguma dessas em qual intervalo em posso barba que a gente tem que procurar o e animações dá pra gente fazer rir cada página do nosso árvore pode ser implementado por um vetor ordenado e daí para a gente encontrar se achava que a gente está interessado tá na área o Buzz para fazer o que eu posso fazer uma busca vinagre por exemplo tá então poucas verificações por página a gente consegue determinar qual que é se fosse a chave que ele está

procurando tá naquele naquela página ou seja tem que descer para outros níveis para continuar nossa busca então sentem parecer E aí essa busca que você vai fazer aqui dentro né e cada página Com certeza pode tem várias técnicas implementar Essa é a manter esse vetor ordenado aqui para depois usar uma busca binária para fazer essa verificação rapidamente é uma ideia interessante mas não é necessariamente a única forma de implementar veja aqui árvore de ela é quase momento algoritmo tem vários pontos onde você várias faz pontos da implementação da árvore bem que você pode usar várias

estratégias diferentes para resolver tá então é interessante ver a árvore B com esse tipo de algorítimo que tem vários pontos que você pode customizar na rede aqui e do pronto você tá resolvendo agora só uma observação a gente falar de inserção e é para quem está pensando que vocês pensam acho que vocês perceberam que a gente tem três nós internos que não estão respeitando essa propriedade e que a gente tem que ter no mínimo M sobre duas Chaves em todos os nós que não são a raiz Só Por uma questão que a gente vai ver

agora na inserção é impossível respeitar essa propriedade para quando M = 4 ou menor entretanto os procedimentos que eu vou explicar para vocês agora garantem que desde que o m seja o maior do que 4 a gente consegue garantir que no mínimo a gente vai ter M sobre duas Chaves em cada página tá vou vencer são tão somente a investigar como que fica a inserção dessas Chaves aqui numa árvore-b degrau quatro então e é os nossos Marcos pedido quatro são dessa a gente vai representar com esse gráfico aqui tá inclusive que que eu vou fazer

eu vou pegar e vou deixar um desse aqui Escondidinho cantinho que eu vou copiar esse foi várias vezes para ficar mais rápido de fazer árvore tá então vez que a gente tem espaço a gente tem quatro espaços para para para deixar valor mas o último é só um temporário a gente vai usar só se no caso que a gente for fazer então o split tá a gente vai ver Exatamente isso quer dizer que a gente tiver um que a gente precisar fazer as operações bom então vamo lá então inicialmente a gente tem uma chave vazio

onde tem uma árvore vazia e a gente vai Inserir a chave s bom então a partir de uma árvore vazia gente vai ser deixar viesse chave é a chave S então simplesmente vai ter isso aqui a partir da chave essa então e a gente vai inserir masha foi seria a chave e nessa árvore que só tenho essa Eu lembro que a gente vai manter já coordenado esse só uma das formas de projetar pessoa pode ser que você não mantém ordenado e sempre verifique todos os fatos não tem problema também E então como ficou bom fazer

danado só fica e e esse aqui bem uma propriedade está sendo violado toma continuar fazendo inserção agora vamos inserir sim ou não e a chave ou depois desistiu da chave a gente vai ficar com a e s e agora que vai acontecer alguma coisa interessante né quando a gente conhecia Xavier o que vai acontecer é só quando a gente pega a chave é eu ia ficar com isso aqui não e r vejo que a gente acabou de usar aquela aquele espaço temporário E lembra que uma das propriedades da árvore B é que cada não né

Cada página tem o máximo e menos ou baixar Então você gente lembrar só Pode ocupar três desses quatro espaços consideramos que esse passo aqui então é só o espaço tempo parar com que a gente resolve isso a gente resolve isso da seguinte forma tá vai pegar e vai fazer uma operação chamada de Split eu como que fica com que essa operação split tá operações Pit muito parecido com operação split que a gente fez quando a gente tem uma árvore dois três só a gente vai pegar vai visualizar aqui com se a gente tivesse como se

tivesse pegando né metade da e dividindo essa página o mei oi e daí a gente vai pegar e subir o último elemento da primeira metade para ser para uma sob árvore que esteja assim no caso aqui a gente tem só uma uma página na árvore ter Então esse nós só esse essa chave que sozinha e vai se tornar a única chave de uma nova raiz como a subir árvore esquerda sendo essa página aqui e assoviar de direita sendo essa outra metade tá então as palavras de perder algo assim ó bom então eu disse em outras

palavras vai ter uma Novaes Ah tá então não vai fica aí vai ter Metade dos elementos daquela página vai ficar auxiliares que a outra metade vai ficar numa sobre árvore direito e quem que vai subir vai subir o último elemento da primeira metade Então vai subir Oi aqui e vai ficar o aqui embaixo esquina souber pesqueiro e RS nosso Barbie direita tá E daí veja que o link que está indicando os alimentos que são menores do que o menor do que a menor chave aqui na raiz voltar para isso que não voltar a pressão subir

árvore que tem as menores Chaves e esse outro link vai estar referenciando as chaves que são maiores que eu falei para vocês agora pouco quando a gente tem uma árvore B de degrau quatro Nem sempre é possível a gente respeitar essa propriedade de ter no mínimo M sobre dos nossos isso é porque né suplementação específicas e aqui aonde as chaves ficam muito com os dados né equivalentes né os valores que podem ser aquela chave tá é quando a gente faz do split a gente sobe a gente a quatro ele mexe quando a gente faz o

split a gente sobe o último elemento do primeiro metade Então nesse nível aqui no nível onde a gente vai ter todas as chaves e certa que subiu a gente sempre vai ter só três chaves que vieram daquela página que foi feito Sprint ainda não tem como as duas sob árvores que foram criadas terem M sobre dois porque uma das quatro foi para cima e automaticamente Só vai sobrar uma chave para a esquerda e duas chaves para direitos tá então por isso que não tem como de respeitar essa propriedade de no mínimo ele sobre duas Chaves

é para 1 m menor ou igual a quatro tá no caso do Neymar quatro daí aí vai funcionar tranquilo só essa mesma mesmo procedimento e vocês aqui sob o último elemento da primeira metade nesse caso não não dá para acontecer isso por causa que com m = 4 vai ficar três elementos em baixo vou subir baixar então é possível ficar impossível ficar ele sobre dois aqui na primeira metade da pessoa então é é Era exatamente por isso aqui que aquela propriedade não podia ser respeitava para quando o m = 4 então agora praia de maior

que quatro aí aquela propriedade ver se respeitada Sem problema nenhum pelo pela sua split tudo bem O que que eu vou continuar fazer as inserções então eu escrevendo Sério né agora vou inserir você tá Então como que fica a inserção você nem vou eu vou fazer passo a passo aí para ficar fácil depois nos acompanhar né então se a gente fizer inserção É né agora o próximo passo Nossa vou fazer a inserção da chave C né bom então a gente vai ter a partir daquela daquela árvore interior né hoje a gente vai ser você bem

você ele é antes doer é igual aí ou depois de antes doer Então tem que estar nessa subir página aqui nessa sob a árvore ela essa página aqui dessa página para baixo tá aí vejo que eles estavam foi olho tá aí folha ainda não é não achei aí pro salão está cheio a gente pode simplesmente inserir você na posição correta quer logo depois só que Beta então acho que não né então vamos lá para segunda ou agora vou Inserir a próxima letra né Depois você é o ar que E aí e hoje a gente vai

ser devagar aqui tem o HR antes doer é igual aí ou depois ler a gente sabe que o HP é depois doido tem que estar nosso garve nessas lugar que corresponde os elementos que são maiores que então a gente vai carregar seu página aqui pegando já perguntar esse aqui é um foi então sim é um folha e tem espaço mas tem espaços disponíveis a gente pode simplesmente seria olhar que nos preocupar com os clientes né então onde que o h é menor do que RS estão simplesmente né empurra o RS uma posição para frente e

insere o agarrou aqui na primeira posição tá então search já enchemos todas as letras da palavra search que é busca inglês né Agora vamos sei a letra x é a chave x aqui na nossa ó o X é antes de é igual aí ou depois depois jeito tem que estar nessa subir árvore que não tente carrega essa página e agora a gente vai veja que esse carro aqui é um folha lá então vamos seria um X aqui em ordenado A então como x e depois de todas as letras de isso vai ficar mas vejo que

agora a gente está violando a propriedade de que numa árvore-b de ordem e cada nota tem que ter no máximo e menos uma chave então a gente tem que de alguma forma resolver esse problema aí a gente já viu que a forma de resolver esse problema é por meio da operação split né então não operações print que a gente vai fazer pessoal novamente a gente vai pegar aquela página que tá tendo overflow né que a página que tá mais cheia do que deveria a gente vai criar então duas novas lembrar de uma nova página né

deixar os m sobre ou menos um alimentos na primeira página página da esquerda e copiar os outros elementos para Nova página e daí a gente vai subir o r que para cima tá tocando que fica isso aí E aí eu não vou fazer qualquer ação de Split E então quem vai subir vai ser o r é o último alimento da primeira metade sobe e a gente cria uma nova página então que os elementos que estavam na segunda metade que Oeste São ser colocado nessa nova E desde que a gente tem que dar ir fazer como

a gente subiu é e a gente sabe que eu era o último elemento né da primeira metade não sabe que todo mundo que tá para frente é bem depois de air então é lógico que esse link agora que não tava contando para ninguém agora vai apontar para essa nova página aqui E aí e com tanta talvez que agora não é muito isto é uma árvore bem que não tá né o que não está infringindo nenhuma das propriedades de árvore ver tudo bem pessoal o sonho capturando a hora que a gente encheu ou a página que

a gente vai fazer a gente vai dividir essa página e duas de que forma vai criar uma nova página que vai ter todas as chaves da segunda metade tá e a gente vai pegar a o último último a chave que estava na primeira metade de subir ela para o nível anterior a gente sabe que como a última chave da metade esquerda subiu pro pro plantei sabe o que é direita a gente tem que pendurar Então os elementos que estão na nova página 1 é tão certinho x agora vamos seguir uma MP E aí bom Então

como que a gente vai fazer pessoal bem o a administração muito parecida né com da chave da árvore dois três quatro vinagre né é percorrer descobri que a descobrir qual subir árvore que se encaixa Ué então PM antes de ir e entre ele é ou é ou depois de é esse aí tá então tem que estar nessa Sugar por aqui veja quem chegou num folha e a gente pode então simplesmente é inserir o m aqui nesse foi tão ele vem depois vejo como a gente não acabam transbordou né a quantidade máxima que a gente pode

ter de Chaves aqui nessa página a gente simplesmente pode ir tão terminar nossa ser sopa tem mais nada que fazer agora vamos seguir a chave p e novamente gente vai descobrir onde veja em qual página que a gente tem que ser iupi né então o pé antes doer entre o erro é ou depois do é ou é igual aí ué é entre é Tá bom então a gente vai descer gente sabe que a gente tem que inserir nessa sub-árvore aqui tá começa a subir a árvore aqui é simplesmente o nosso olho que a gente vai

fazer pessoal só uma página que não foi a gente pode simplesmente seria o quê que não possou correto aí para eu ver aqui depois do Remo e veja que a gente não transbordou também quantidade máxima de Chaves E aqui nessa parte Então a nossa inserção tá tá terminado comentando Inserir a chave L agora bom então onde que vai Xavier pessoal o ele antes do rei é igual a e entre e R é igual é ou é depois de entre é Tá bom então ele não sabe que tem que ir nessa página aqui também então vamos

inserir veja que é uma página foi tá câncer é uma parte da folha a gente tem que fazer o que tem que pegar aí um incêndio é lindo lugar Propriá não tinha ficarelli M as vezes que depois a inserção da chave l a gente transbordou a quantidade máxima a gente ultrapassou a quantidade máxima de Chaves que a gente podia ter nessa página que era o Márcio como a gente tem é igual a 4 pode ter no máximo é é menos uma chave que é três chaves em cada uma tem que a gente vai fazer pente

só novamente a operação split tá então como fica operações split nesse caso aqui Pedro é a mesma coisa pra gente ficar com a gente vai considerar que a gente vai cortar essa página ao meio onde em criar uma nova página para conter essas chaves e valores aqui da segunda metade e vai subir o último a chave da primeira da primeira metade do nível superior então vai ficar dessa forma aqui ó E aí E aí e vai subir em vejo que como vai subir entre UERJ onde que ele vai botar um logo depois do é então

o ele vai subir para cá o raio R é ficar direito nesse nessa página que a gente vai ter só o h beleza I e II e os elementos MP e e Me desculpe Henrique da subida aqui era o ele não é pessoal eu quero Sky Net arrumar maior chave da primeira metade Desculpa tá Não quero pouco de vocês e daí depois do ele vai ficar um Ipê bom então depois não é o show depois vai é bem pessoal Então olha só mas só para ficar mais claro né que você quer é tanta coisa que

eu tenho que desenhar que às vezes não se perde pouquinho né então mas a ideia seguinte Acabou de ser de com ele ou ele vai aqui entre é ele vai nem se for aqui sofre de transbordo se é pra gente precisa fazer explica resolver aí a gente corta na metade é verdade que a gente vai fazer não é muito cortar de ver como se estivesse cortando mas a ideia é que a gente vai criar uma nova página com que vai ter todas as chaves que tiver na segunda metade o MP veio ver direitinho né a

gente vai subir a maior chave da primeira metade para cima né eu vejo que eu sobre o Hélio ela e ficou antes do Oeste logicamente a única posição que ele pode ficar na verdade porque como ele era é como ele tava na sob a árvore que era entre erra ele não tem como ser maior que é a então ele tem que ver o lugar não é fazer só isso ele veio para cá daí fica todo mundo eu quero que subiu lá na página já tava não precisa tirar na verdade essa parte continua sendo a mesma

que vejo que ela é que tá sendo referenciada entre R né Então pessoal esse é mais um split que acontece aqui agora vai ficar bem certinho exemplo eu vou mostrar para vocês que acontece quando a gente tem um Split na raiz quando a árvore não tem só a raiz igual a gente viu anteriormente e agora a gente vai ter um split que vai vir lá do último nível quer fazer a árvore crescer mais um vídeo para ser tá bom é isso que a gente vai ver ela o Misterio então a chave y un G1 bom

então aonde vai achar vídeo né Y é antes doer é igual a e entre l = l entre l e r = r ou é maior que vem depois de vem depois é grave trabalho peço brava eu só tenho a parte Então faz seria Y nela né porque amanhã a gente vai ter essa página é é uma folha a gente vai ser ido só que no lugar 5 e nada mais acontece porque a gente não tá desrespeitando nenhuma das propriedades dar bebê nós vamos seguir achar dizer é só tirar tenho acabou de ser Il y

a o Misterio já avisei olha só que interessante que vai acontecer quando a gente seria a chave ser tá então a gente sabe que o z vem na ideia maior chave que a gente está considerando aqui então a gente tem que ver na última parte certa e daí faz seria você ela na posição certa lá no nosso nosso não foi só que vende seguinte veja que essa página agora ela está violando a propriedade de que a quantidade máxima que a gente pode ter e Chaves no mod grau m&m medo né então se o nosso =

4 a gente tá com 4 Chaves tem que ter no máximo 3 A gente tem que fazer operação de Split então para resolver né Essa essa violação da propriedade da água de bebê então eu coloquei ficar pessoal bem que vai acontecer o seguinte e vai primeiro criar um novo ló e no final aqui que vai ter só as maiores chaves da segunda metade em todas as chaves da segunda metade né da página que a gente está fazendo Sprint vai ter só isso só isso aqui Oi gente vai pegar a maior chave da primeira metade da

página que a gente está fazendo espetinho é o x e a gente faz subir ela dormir anterior só olha só que interessante que a gente vai ter agora pessoal não fiz vai subir Oi e a gente vai conectar então e agora esse link aqui para trocar a gente que desculpa de criar Tá ok então eu vejo que no último nível agora ninguém está violando as propriedades da árvore P O problema é que o x que subiu tá agora ele tá fazendo esse nó né essa página violada por causa da árvore b então quê que a

gente vai ter que fazer isso pra gente também pessoal tá vejo que esse algoritmo ele ortogonal né em muitos casos assim tá ele simplesmente Funciona recursivamente porque tudo que a gente faz o split de sinnott que percebendo que ele é um raiz tem que eu só vou mudar nada tá excesso aqui como não tem nem um nível acima dessa página que que a gente vai ter que fazer até criar uma nova página para conter uma única chave da Raíssa tá mas isso não é um problema é igualzinho o que a gente fez quando a gente

nesse exemplo aqui ó que eu mostrei pra vocês é que foi o primeiro exemplo onde a gente fez o split e os print eram da Raíssa então talvez a gente só criar uma única é a mais para conter a segunda metade da página que foi split né nesse caso aqui ó eu tinha precisar criar também uma página mais para conter a chave da raiz tá então como vai ficar bem vai ficar mal e a gente vai subir Esse é ele é o maior da primeira metade Então vai subir L para raiz E aí E aí

I spent as duas páginas aqui ó Ah que bom com as outras Chaves do Norte está sendo está sendo dividir então o ele vai ficar aqui ó e o RX vai ficar aqui só e as páginas que estavam sendo referenciados por pelas duas páginas e pela baixa e pela página é registo né então continuar sendo referenciado pelas mesmas Chaves tá pessoal Então veja aqui esse esse passo para esse aqui parece muito mágico Mas é bem simples tá quando a gente vai fazendo split da raiz gente vai ter que criar um uma página para conter só

a chave que subiu né o l e mais uma nova página para conter então é a segunda metade das chaves e dos dados correspondentes a aquela página que a gente tá dividindo né então o RX vem para cá o e continuou para cá e sumiu era eu vejo que é muito muito muito semelhante aos outros espíritos que a gente fez outros Livres é certo que aqui que precisa criar e como não tem nenhum nível acima da página que a gente tá dividindo né gente tem que criar então uma página para ser a nova raiz da

nossa árvore tá então o pessoal é é assim que é feito inserção numa árvore-b tá na verdade Demorou tudo isso explicar por que eu fui foi desenhando junto com vocês mostrando pra vocês a ideia né vezes até ajuda a sedimentar melhores conhecimento as vezes que não tem segredo nenhum é praticamente uma nos assim mas generalização né da implementação da árvore dois três só que para quando você pode ter mais do que no máximo do Chaves por não você pode ter até ele menos uma chave pornô assim como a gente viu no começo do vídeo as

árvores B elas foram pensadas para que a gente pudesse tem uma estrutura de chave o valor que pudessem implementados em que ela todos tivessem memória principal ou seja iria suportar e bilhões né de chá de Oi e aí deck o pessoal teve foi fazer com que cada nova ela sabe fosse na verdade um Nokia comece mais pares chave-valor né e fazer estrutura de forma que a gente pudesse então carregar pedaços né página essas páginas da nossa estrutura conforme a gente fosse precisando Então vai encontrar qualquer elemento na nossa árvore de bebê o que a gente

quer fazer Minimizar na verdade a quantidade de vez que a gente tem que carregar páginas e quem sabe que a tarefa de carregar uma página da memória secundária é algo que a gente deve evitar ao máximo a gente consegue minimizar a quantidade de vezes que a gente tem que fazer né Abrir essas páginas a gente consegue melhorar o máximo desempenho tá em uma forma da gente tentar garantir que eu tinha acesso a quantidade mínima de vezes o disco para fazer uma única busca é fazer o quê pessoal é garantir que a nossa árvore tá perfeitamente

balanceado tá é por isso então que a gente tecla Oi gente que é que não sabes perfeitamente balanceada então falta mais uma pergunta para te responder tem qual que é a relação da quantidade de nós que quando a postagens de páginas que eu vou ter que visitar a partir da raiz sabendo qual que é o grau da minha árvore B bem pessoal acontece que se o grau dos nossos páginas por m tá a gente vai ter que fazer no máximo log e na base m de L onde é a quantidade de Chaves que tá gravado

aqui na nossa árvore bem essa é a quantidade máxima de descidas que de páginas que a gente vai ter que carregar né em sequência para para achar então uma chave se ele foi igual a 1000 por exemplo tá a gente vai precisar se a gente tiver um bilhão de Chaves A gente vai precisar no máximo ler Quatro páginas para encontrar qualquer chave que tiver não árvore B indica o meu lá para o portão ou falei para vocês isso é algo Espetacular também falei para vocês no começo da aula que existem várias variações de aves B

tá na hora que vem a gente vai ver uma avaliação bastante comum utilizado na construção de índices de banco de dados tá que a árvore bem mais bem mais por hoje é só e até a próxima