´Arvores B
´Atila Camurc¸a
Samir Coutinho
Tunay Ara´ujo
27 de junho de 2013
Sumary
1 Introduc¸˜ao
2 Motivac¸˜ao
3 Definic¸˜ao
4 Operac¸˜oes B´asicas
5 Exemplo
6 Utilizac¸˜ao
PostgreSQL
7 Referˆencias
Introduc¸˜ao
Sabemos que em relac¸˜ao a mem´oria de computador existe uma hierarquia
de velocidade de acesso, mem´orias ca...
Motivac¸˜ao
Quando os dados s˜ao muito grandes para caber na mem´oria principal,
eles devem se expandir para o disco. O ac...
Definic¸˜ao
´Arvores B s˜ao ´arvores de pesquisa balanceadas projetadas
especificamente para serem armazanadas em discos mag...
Altura
O n´umero de acessos ao disco ´e proporcional a altura da ´Arvore B.
O pior caso da altura de uma ´Arvore B ´e
h ≤ ...
Operac¸˜oes B´asicas
Sempre mantemos a ra´ız na mem´oria principal, assim um
DISK-READ da ra´ız nunca ser´a necess´ario.
Q...
Operac¸˜oes B´asicas
O n´umero de execuc¸˜ao de um algoritmo de ´arvores B ´e determinado,
principalmente, pelo n´umero de...
Operac¸˜oes B´asicas
1. B-TREE-SEARCH
2. B-TREE-INSERT
3. B-TREE-CREATE
4. B-TREE-DELETE
B-TREE-CREATE
Para construir ´arvores B utilizamos B-TREE-CREATE para criar um n´o
raiz vazio e depois chamamos B-TREE-INS...
B-TREE-INSERT
O n´umero de acessos a disco de B-TREE-INSERT ´e O(h) pois
apenas O(1) operac¸˜oes disk-read/write s˜ao feit...
Inserc¸˜ao de elemento (split)
A inserc¸˜ao nas ´arvores B ´e relativamente mais complicada, pois,
precisamos inserir a no...
B-TREE-SPLIT-CHILD
A nova chave sempre ´e inserida em uma folha.
A inserc¸˜ao ´e feita em um ´unico percurso na ´arvore, a...
B-TREE-INSERT-NONFULL
O c´odigo a seguir faz uso do procedimento
B-TREE-INSERT-NONFULL, que ´e respons´avel pela inserc¸˜a...
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
B-TREE-DELETE
Caso 1: envolve delec¸˜ao da chave de uma folha. Restando t − 1
chaves.
Caso 2: se a chave k estiver no n´o ...
Utilizac¸˜ao
Muitos sistemas de bancos de dados usam ´arvores B ou variac¸˜oes de
´arvores B para armazenar informac¸˜oes....
PostgreSQL
PostgreSQL usa ´arvores B nos seus ´ındices (INDEX). ´Indices s˜ao usados
primariamente para aumentar a perform...
PostgreSQL
´Arvores B s˜ao melhor utilizadas quando um ´ındice involve comparac¸˜oes
como <, <=, =, >=, >
Exemplo
PostgreSQL
CREATE TABLE not_indexed_table
(
id integer NOT NULL
)
WITH (
OIDS=FALSE
);
ALTER TABLE not_indexed_tab...
Exemplo
PostgreSQL
CREATE TABLE indexed_table
(
id integer NOT NULL,
CONSTRAINT indexed_table_pkey PRIMARY KEY (id)
)
WITH...
Exemplo
PostgreSQL
INSERT INTO not_indexed_table (id)
SELECT GENERATE_SERIES(1, 100000);
INSERT INTO indexed_table (id)
SE...
Exemplo
PostgreSQL
EXPLAIN ANALYZE SELECT COUNT(*) FROM not_indexed_table;
-- sa´ıda
Aggregate (cost=1572.00..1572.01 rows...
Exemplo
PostgreSQL
EXPLAIN ANALYZE SELECT COUNT(*) FROM indexed_table;
-- sa´ıda
Aggregate (cost=1643.00..1643.01 rows=1 w...
Exemplo
PostgreSQL
EXPLAIN ANALYZE SELECT * FROM not_indexed_table
WHERE id < 12;
-- sa´ıda
Seq Scan on not_indexed_table
...
Exemplo
PostgreSQL
EXPLAIN ANALYZE SELECT * FROM indexed_table
WHERE id < 12;
-- sa´ıda
Index Only Scan using indexed_tabl...
Exemplo
PostgreSQL
Tabela Tamanho
not indexed table 3168 kB
indexed table 4936 kB
PostgreSQL
Da documentac¸˜ao do PostgreSQL:
Adding a primary key will automatically create a unique btree
index on the col...
Referˆencias
http://www.depesz.com/2010/09/09/
why-is-my-index-not-being-used/
http://www.thegeekstuff.com/2009/05/
15-adv...
of 43

Árvores B

Apresentação sobre árvores B com exemplo usando PostgreSQL
Published on: Mar 4, 2016
Published in: Technology      
Source: www.slideshare.net


Transcripts - Árvores B

  • 1. ´Arvores B ´Atila Camurc¸a Samir Coutinho Tunay Ara´ujo 27 de junho de 2013
  • 2. Sumary 1 Introduc¸˜ao 2 Motivac¸˜ao 3 Definic¸˜ao 4 Operac¸˜oes B´asicas 5 Exemplo 6 Utilizac¸˜ao PostgreSQL 7 Referˆencias
  • 3. Introduc¸˜ao Sabemos que em relac¸˜ao a mem´oria de computador existe uma hierarquia de velocidade de acesso, mem´orias cache e de registro s˜ao mais velozes que mem´orias RAM, que s˜ao mais velozes que HDs. Podemos utilizar algor´ıtmos que especificamente sejam r´apidos ao acessar HDs.
  • 4. Motivac¸˜ao Quando os dados s˜ao muito grandes para caber na mem´oria principal, eles devem se expandir para o disco. O acesso ao disco ´e muito custoso em comparac¸˜ao com uma instruc¸˜ao t´ıpica. O n´umero de acessos ao disco vai preponderar o tempo de execuc¸˜ao. O objetivo das ´Arvores B ´e criar uma ´arvore de busca que ir´a minimizar os acessos ao disco.
  • 5. Definic¸˜ao ´Arvores B s˜ao ´arvores de pesquisa balanceadas projetadas especificamente para serem armazanadas em discos magn´eticos. Medimos o desempenho pela quantidade de tempo de computac¸˜ao que consomem, mas tamb´em pela quantidade de acesso a disco que s˜ao realizadas.
  • 6. Altura O n´umero de acessos ao disco ´e proporcional a altura da ´Arvore B. O pior caso da altura de uma ´Arvore B ´e h ≤ logt n + 1 2 ⇔ O(logt n)
  • 7. Operac¸˜oes B´asicas Sempre mantemos a ra´ız na mem´oria principal, assim um DISK-READ da ra´ız nunca ser´a necess´ario. Qualquer n´o passado como parˆametro j´a deve ter sofrido um DISK-HEAD. Qualquer n´o deve ter mudado com um DISK-WRITE.
  • 8. Operac¸˜oes B´asicas O n´umero de execuc¸˜ao de um algoritmo de ´arvores B ´e determinado, principalmente, pelo n´umero de operac¸˜oes DISK-WRITE e DISK-READ. A quantidade de acessos ao disco ´e diretamente proporcional ao fator de ramificac¸˜ao.
  • 9. Operac¸˜oes B´asicas 1. B-TREE-SEARCH 2. B-TREE-INSERT 3. B-TREE-CREATE 4. B-TREE-DELETE
  • 10. B-TREE-CREATE Para construir ´arvores B utilizamos B-TREE-CREATE para criar um n´o raiz vazio e depois chamamos B-TREE-INSERT para adicionar novas chaves. Ela exige O(1) operac¸˜oes de disco e tempo de CPU O(1).
  • 11. B-TREE-INSERT O n´umero de acessos a disco de B-TREE-INSERT ´e O(h) pois apenas O(1) operac¸˜oes disk-read/write s˜ao feitas entre duas chamadas consecutivas de B-TREE-INSERT-NONFULL. O tempo total de cpu ´e O(th) = O(t logt n). Observac¸˜ao o split na raiz ´e o unico jeito de aumentar a altura da ´arvore B. Ao contr´ario das ´arvores bin´arias, o crescimento se d´a na raiz em vez das folhas.
  • 12. Inserc¸˜ao de elemento (split) A inserc¸˜ao nas ´arvores B ´e relativamente mais complicada, pois, precisamos inserir a nova chave no n´o correto da ´arvore, sem violar suas propriedades. Como procedemos se o n´o est´a cheio? Se estiver cheio deve separar (split) o n´o em torno do elemento mediano, criando outros dois n´os que n˜ao violam as definic¸˜oes de ´arvore. O elemento mediano ´e promovido, passando a fazer parte do n´o pai daquele n´o.
  • 13. B-TREE-SPLIT-CHILD A nova chave sempre ´e inserida em uma folha. A inserc¸˜ao ´e feita em um ´unico percurso na ´arvore, a partir da raiz at´e uma das folhas. O procedimento B-TREE-SPLIT-CHILD ´e usado para garantir que a recurs˜ao nunca desc¸a em um n´o cheio.
  • 14. B-TREE-INSERT-NONFULL O c´odigo a seguir faz uso do procedimento B-TREE-INSERT-NONFULL, que ´e respons´avel pela inserc¸˜ao da chave em um n´o n n˜ao cheio. B-TREE-INSERT-NONFULL, insere a chave k no n´o x, caso este seja uma folha, caso contr´ario, procura o filho adequado e desce a ele recursivamente at´e encontrar a folha onde deve inserir k.
  • 15. Exemplo
  • 16. Exemplo
  • 17. Exemplo
  • 18. Exemplo
  • 19. Exemplo
  • 20. Exemplo
  • 21. Exemplo
  • 22. Exemplo
  • 23. Exemplo
  • 24. Exemplo
  • 25. Exemplo
  • 26. Exemplo
  • 27. Exemplo
  • 28. Exemplo
  • 29. Exemplo
  • 30. B-TREE-DELETE Caso 1: envolve delec¸˜ao da chave de uma folha. Restando t − 1 chaves. Caso 2: se a chave k estiver no n´o x e x ´e um n´o interno. Caso 3: se a chave n˜ao estiver presente no n´o interno x.
  • 31. Utilizac¸˜ao Muitos sistemas de bancos de dados usam ´arvores B ou variac¸˜oes de ´arvores B para armazenar informac¸˜oes. Um deles ´e o PostgreSQL (http://www.postgresql.org/).
  • 32. PostgreSQL PostgreSQL usa ´arvores B nos seus ´ındices (INDEX). ´Indices s˜ao usados primariamente para aumentar a performance do banco de dados. Al´em de ´Arvores B o PostgreSQL oferece suporte a: HASH GiST (Generalized Search Tree) SP-GiST (Space-Partitioned - Generalized Search Tree) GIN (Generalized Inverted Index)
  • 33. PostgreSQL ´Arvores B s˜ao melhor utilizadas quando um ´ındice involve comparac¸˜oes como <, <=, =, >=, >
  • 34. Exemplo PostgreSQL CREATE TABLE not_indexed_table ( id integer NOT NULL ) WITH ( OIDS=FALSE ); ALTER TABLE not_indexed_table OWNER TO postgres;
  • 35. Exemplo PostgreSQL CREATE TABLE indexed_table ( id integer NOT NULL, CONSTRAINT indexed_table_pkey PRIMARY KEY (id) ) WITH ( OIDS=FALSE ); ALTER TABLE indexed_table OWNER TO postgres;
  • 36. Exemplo PostgreSQL INSERT INTO not_indexed_table (id) SELECT GENERATE_SERIES(1, 100000); INSERT INTO indexed_table (id) SELECT GENERATE_SERIES(1, 100000);
  • 37. Exemplo PostgreSQL EXPLAIN ANALYZE SELECT COUNT(*) FROM not_indexed_table; -- sa´ıda Aggregate (cost=1572.00..1572.01 rows=1 width=0) (actual time=73.198..73.198 rows=1 loops=1) -> Seq Scan on not_indexed_table (cost=0.00..1336.20 rows=94320 width=0) (actual time=0.023..38.878 rows=100000 loops=1) Total runtime: 73.239 ms
  • 38. Exemplo PostgreSQL EXPLAIN ANALYZE SELECT COUNT(*) FROM indexed_table; -- sa´ıda Aggregate (cost=1643.00..1643.01 rows=1 width=0) (actual time=69.939..69.940 rows=1 loops=1) -> Seq Scan on indexed_table (cost=0.00..1393.00 rows=100000 width=0) (actual time=0.014..35.571 rows=100000 loops=1) Total runtime: 69.974 ms
  • 39. Exemplo PostgreSQL EXPLAIN ANALYZE SELECT * FROM not_indexed_table WHERE id < 12; -- sa´ıda Seq Scan on not_indexed_table (cost=0.00..1643.00 rows=10 width=4) (actual time=0.020..17.527 rows=11 loops=1) Filter: (id < 12) Rows Removed by Filter: 99989 Total runtime: 17.555 ms
  • 40. Exemplo PostgreSQL EXPLAIN ANALYZE SELECT * FROM indexed_table WHERE id < 12; -- sa´ıda Index Only Scan using indexed_table_pkey on indexed_table (cost=0.00..8.45 rows=11 width=4) (actual time=0.022..0.028 rows=11 loops=1) Index Cond: (id < 12) Heap Fetches: 11 Total runtime: 0.053 ms
  • 41. Exemplo PostgreSQL Tabela Tamanho not indexed table 3168 kB indexed table 4936 kB
  • 42. PostgreSQL Da documentac¸˜ao do PostgreSQL: Adding a primary key will automatically create a unique btree index on the column or group of columns used in the primary key. Adicionando uma chave prim´aria ir´a automaticamente criar uma ´Arvore B de ´ındice ´unico na coluna ou grupo de colunas usadas na chave prim´aria. http: //www.postgresql.org/docs/9.0/static/ddl-constraints.html
  • 43. Referˆencias http://www.depesz.com/2010/09/09/ why-is-my-index-not-being-used/ http://www.thegeekstuff.com/2009/05/ 15-advanced-postgresql-commands-with-examples/ http://ats.oka.nu/b-tree/b-tree.manual.html http://www.postgresql.org/docs/9.0/static/ ddl-constraints.html T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Pr´atica, 2002 http: //www.lcad.icmc.usp.br/˜nonato/ED/B_arvore/btree.htm http://www.di.ufpb.br/lucidio/Btrees.pdf

Related Documents