Meu conhecimento de bancos de dados e SQL é baseado principalmente em aulas universitárias. De qualquer forma, passei poucos meses (quase um ano) em uma empresa, onde trabalhava com banco de dados.
Li poucos livros e participei de poucos treinamentos sobre bancos de dados como MySQL, PostgreSQL, SQLite, Oraclee também alguns nonSQL dbcomo nós MongoDB, Redis, ElasticSearchetc.
Bem como eu disse, sou iniciante, com muitos desconhecimentos mas hoje, alguém me disse algo, o que vai totalmente contra o meu conhecimento de iniciante.
Deixe-me explicar. Vamos pegar o banco de dados SQL e criar uma tabela simples Personcom poucos registros dentro:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23
Agora, é a parte que eu gostaria de focar - idé o arquivo INDEX.
Até agora, pensei que funcionasse assim: quando uma tabela está sendo criada, o INDEXestá vazio. Quando estou adicionando um novo registro à minha tabela, INDEXele está sendo recalculado com base em alguns algoritmos. Por exemplo:
Agrupando um a um:
1 ... N
N+1 ... 2N
...
XN+1 ... (X+1)N
então, para o meu exemplo com size = 11 elementse N = 3ficará assim:
id | name | age
-----------------
1 | Alex | 24 // group0
2 | Brad | 34 // group0
3 | Chris | 29 // group0
4 | David | 28 // group1
5 | Eric | 18 // group1
6 | Fred | 42 // group1
7 | Greg | 65 // group2
8 | Hubert | 53 // group2
9 | Irvin | 17 // group2
10 | John | 19 // group3
11 | Karl | 23 // group3
Então, quando estou usando query SELECT * FROM Person WHERE id = 8ele vai fazer alguns cálculos simples 8 / 3 = 2, então temos que procurar esse objeto group2e então essa linha será retornada:
8 | Hubert | 53
Essa abordagem funciona no tempo em O(k)que k << size. Claro, um algoritmo para organizar linhas em grupos é com certeza muito mais complicado, mas acho que este exemplo simples mostra meu ponto de vista.
Agora, gostaria de apresentar outra abordagem, que me foi mostrada hoje.
Vamos pegar mais uma vez esta tabela:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23
Agora, estamos criando algo semelhante a Hashmap(na verdade, literalmente é um mapa de hash) que mapeia idpara addressuma linha com esse id. Digamos:
id | addr
---------
1 | @0001
2 | @0010
3 | @0011
4 | @0100
5 | @0101
6 | @0110
7 | @0111
8 | @1000
9 | @1001
10 | @1010
11 | @1011
Então agora, quando estou executando minha consulta:SELECT * FROM Person WHERE id = 8
ele mapeará diretamente id = 8para o endereço na memória e a linha será retornada. Claro que a complexidade disso é O(1).
Então agora, eu tenho algumas perguntas.
1. Quais são as vantagens e desvantagens de ambas as soluções?
2. Qual deles é mais popular nas implementações de banco de dados atuais? Talvez dbs diferentes usem abordagens diferentes?
3. Ele existe em bancos de dados não SQL?
Agradeço antecipadamente
COMPARAÇÃO
| B-tree | Hash Table
----------------------------------------------------
---------------- one element -------------------
----------------------------------------------------
SEARCHING | O(log(N)) | O(1) -> O(N)
DELETING | O(log(N)) | O(1) -> O(N)
INSERTING | O(log(N)) | O(1) -> O(N)
SPACE | O(N) | O(N)
----------------------------------------------------
---------------- k elements -------------------
----------------------------------------------------
SEARCHING | k + O(log(N)) | k * O(1) -> k * O(N)
DELETING | k + O(log(N)) | k * O(1) -> k * O(N)
INSERTING | k + O(log(N)) | k * O(1) -> k * O(N)
SPACE | O(N) | O(N)
N - número de registros
Estou certo? E quanto ao custo de reconstruir a árvore B e a tabela Hash após cada inserção/exclusão ? No caso da árvore B , temos que alterar alguns ponteiros, mas no caso da árvore B balanceada, é necessário mais esforço. Também no caso da tabela Hash , temos que fazer poucas operações, especialmente, se nossa operação gerar conflitos .