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 .
Você está basicamente descrevendo um índice de árvore B e um índice de hash. Ambos têm um lugar, mas ambos são mais adequados para trabalhos diferentes.
Vantagens e desvantagens
Índices de árvore B (e árvore B+) geralmente são balanceados. Isso significa que procurar um valor sempre levará o mesmo tempo, não importa onde ele caia na árvore (O(log n)). Geralmente, o número de níveis na árvore é limitado, então ela tende a ficar "mais larga" e não "mais profunda". Para pequenos conjuntos de dados, o custo de manutenção e uso da árvore B, no entanto, pode ser maior do que apenas ler todas as linhas. Os índices de árvore B são bons para grandes conjuntos de dados, conjuntos de dados com baixa seletividade ou conjuntos de dados em que você pretende selecionar uma variedade de objetos e não apenas um objeto.
Tabelas de hash são ótimas para pequenos conjuntos de dados. Os índices de hash têm um número predefinido de baldes de hash, dependendo do algoritmo de hash usado. Isso ocorre porque um determinado algoritmo de hash só pode produzir tantos hashes exclusivos, portanto, fica "mais profundo" e não "mais amplo". Depois que o mecanismo de banco de dados encontra o depósito certo, ele percorre todos os objetos nesse depósito para encontrar o que você deseja. Com conjuntos de dados pequenos e altamente seletivos, cada bucket contém um número muito pequeno de objetos e é resolvido rapidamente. Com conjuntos de dados maiores, os baldes ficam muito mais lotados. Portanto, se o objeto que você precisa estiver em um balde pequeno ou próximo ao início do balde, ele retornará bem rápido. Se estiver no final de um balde grande, demora mais. O índice não é balanceado, então o desempenho varia de O(1) a O(n).
Popularidade
Em geral, eu encontrei mais árvores B. Os índices de bitmap também são outra opção para valores com baixa cardinalidade (pense em booleanos ou talvez gênero). Isso vai variar dependendo do seu mecanismo de banco de dados quanto aos tipos de índice disponíveis.
NoSQL
Bancos de dados NoSQL definitivamente suportam índices. A maioria suporta B-tree ou uma variação da B-tree. A maioria parece suportar índices hash também.
Quais são as vantagens e desvantagens de ambas as soluções? A segunda solução não pode realizar varreduras de alcance. É ótimo para selecionar um único ID. Mas e se você quiser ids de 3 a 8? Ele tem que pegar todos os registros individuais que no mundo real não são apenas O(1) * 6 registros para recuperar. Em um grande banco de dados de produção com um índice HashMap, você obteria registros em páginas diferentes, exigindo que você acessasse o disco e lesse seis páginas diferentes na memória.
Em uma estrutura B-Tree, como a sua primeira situação seria realmente implementada, os ids seriam sequenciais no disco e uma única página provavelmente conteria os ids 3 - 8 aumentando a velocidade das varreduras de alcance tornando o acesso individual O(log n) .
Qual deles é mais popular nas implementações de banco de dados atuais? Talvez dbs diferentes usem abordagens diferentes? Não tenho muita experiência em muitos bancos de dados diferentes. Eu sei que o Sql Server usa principalmente B-Trees, mas o SQl 2014 tem alguns novos índices de hash que você pode usar em determinadas tabelas. Eu ouço muitos bancos de dados No Sql e bancos de dados de cache construídos na recuperação de registros individuais também usam índices de hash. Isso faz sentido para caches, pois você deseja o registro do usuário A e não precisa de varreduras de alcance.
Existe em dbs não SQL? Sim. Dando uma olhada rápida na documentação de criação de índice para postgressql, vejo que ele suporta índices Hash e B-Tree, bem como alguns outros.