Arvore b
5428 palavras
22 páginas
´ Arvores BMO637 – Complexidade de Algoritmos II
14 de setembro de 2007
MO637 – Complexidade de Algoritmos II
´ Arvores B
Overview
MO637 – Complexidade de Algoritmos II
´ Arvores B
Overview
S˜o ´rvores balanceadas, desenvolvidas para otimizar o acesso a a a armazenamento secund´rio a
MO637 – Complexidade de Algoritmos II
´ Arvores B
Overview
S˜o ´rvores balanceadas, desenvolvidas para otimizar o acesso a a a armazenamento secund´rio a Os n´s da ´rvore B podem ter muitos filhos. Esse fator de o a ramifica¸˜o ´ determinante para reduzir o n´mero de acessos ca e u ´ a disco. Arvores B s˜o balanceadas, ou seja, sua altura ´ a e O(lg (n))
MO637 – Complexidade de Algoritmos II
´ Arvores B
Overview
S˜o ´rvores balanceadas, desenvolvidas para otimizar o acesso a a a armazenamento secund´rio a Os n´s da ´rvore B podem ter muitos filhos. Esse fator de o a ramifica¸˜o ´ determinante para reduzir o n´mero de acessos ca e u ´ a disco. Arvores B s˜o balanceadas, ou seja, sua altura ´ a e O(lg (n)) ´ Arvores B s˜o generaliza¸oes de ´rvores bin´rias balanceadas a c˜ a a
MO637 – Complexidade de Algoritmos II
´ Arvores B
Armazenamento Secund´rio a
MO637 – Complexidade de Algoritmos II
´ Arvores B
Armazenamento Secund´rio a
Atualmente o armazenamento est´vel ´ feito em discos a e magn´ticos, e o custo de cada acesso (da ordem de mili e segundos) ´ muito alto quando comparado ao acesso ` e a mem´ria RAM (ordem de nano segundos) o
MO637 – Complexidade de Algoritmos II
´ Arvores B
Armazenamento Secund´rio a
Atualmente o armazenamento est´vel ´ feito em discos a e magn´ticos, e o custo de cada acesso (da ordem de mili e segundos) ´ muito alto quando comparado ao acesso ` e a mem´ria RAM (ordem de nano segundos) o Toda vez que um acesso ´ feito, deve-se aproveita-lo da e melhor maneira poss´ ıvel, trazendo o m´ximo de informa¸˜o a ca relevante
MO637 – Complexidade de Algoritmos II
´ Arvores B