SQL INDEX - como funciona?

Meu conhecimento de bancos de dados e SQL é baseado principalmente nas aulas da universidade. De qualquer forma, passei alguns meses (quase um ano) em uma empresa, onde trabalhava com bancos de dados.

Eu li alguns livros e tenho participado em alguns treinamentos sobre bancos de dados, como MySQL, PostgreSQL, SQLite, Oraclee também alguns nonSQL dbs como nós MongoDB, Redis, ElasticSearchetc.

Como eu disse, eu sou iniciante, com muita falta de conhecimento, mas hoje alguém disse algo, o que é totalmente contrário ao conhecimento do meu 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é a INDEX.

Até agora, pensei que funcionasse dessa maneira: quando uma tabela está sendo criada, a INDEXestá vazia. Quando estou adicionando um novo registro à minha tabela, ele INDEXestá sendo recalculado com base em algumas quantidades. Por exemplo:

Agrupando um por um:

1    ... N
N+1  ... 2N
     ...
XN+1 ... (X+1)N

então, para o meu exemplo com size = 11 elementse N = 3será 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

Portanto, quando estou usando a consulta, SELECT * FROM Person WHERE id = 8ele fará alguns cálculos simples 8 / 3 = 2; portanto, precisamos procurar esse objeto group2e, em seguida, essa linha será retornada:

8  | Hubert | 53

Essa abordagem funciona no tempo em O(k)que k << size. Obviamente, um algoritmo para organizar linhas em grupos é com certeza muito mais complicado, mas acho que este exemplo simples mostra meu ponto de vista.

Então, agora, eu gostaria de apresentar outra abordagem, que me foi mostrada hoje.

Vamos tomar novamente 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(de fato, literalmente, é um mapa de hash) que mapeia idpara a addresslinha 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 será mapeado diretamente id = 8para o endereço na memória e a linha será retornada. Claro que isso é complexidade O(1).

Então agora, eu tenho algumas perguntas.

1. Quais são as aventuras e desvantagens de ambas as soluções?

2. Qual deles é mais popular nas implementações atuais de banco de dados? Talvez diferentes dbs usem abordagens diferentes?

3. Existe em dbs 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 o custo da reconstrução da árvore B e da tabela Hash após cada inserção / exclusão ? No caso da árvore B , precisamos alterar alguns indicadores, mas no caso da árvore b equilibrada, é necessário mais esforço. Também no caso da tabela Hash , temos que fazer poucas operações, principalmente 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

Os índices da árvore B (e árvore B +) são geralmente balanceados. Isso significa que procurar um valor sempre levará a mesma quantidade de tempo, independentemente da árvore em que ele cai (O (log n)). Geralmente, o número de níveis na árvore é limitado, por isso tende a ficar "mais amplo" e não "mais profundo". Para conjuntos de dados pequenos, o custo de manutenção e uso da árvore B, no entanto, pode ser mais do que apenas ler todas as linhas. Os índices da árvore B são bons para grandes conjuntos de dados, conjuntos de dados com baixa seletividade ou conjuntos de dados nos quais você deseja selecionar um intervalo de objetos e não apenas um objeto.

As tabelas de hash são ótimas para pequenos conjuntos de dados. Os índices de hash têm um número predefinido de buckets de hash, dependendo do algoritmo de hash usado. Isso ocorre porque um determinado algoritmo de hash pode produzir apenas tantos hashes exclusivos, tornando-o "mais profundo" e não "mais amplo". Depois que o mecanismo de banco de dados encontra o depósito correto, ele percorre todos os objetos desse depósito para encontrar o que você deseja. Com conjuntos de dados pequenos e altamente seletivos, cada bloco contém um número muito pequeno de objetos e é resolvido rapidamente. Com conjuntos de dados maiores, os buckets ficam muito mais lotados. Portanto, se o objeto que você precisa estiver em um pequeno balde ou estiver próximo do início do mesmo, ele retornará bem rápido. Se estiver no final de um balde grande, leva mais tempo. O índice não é equilibrado, portanto, o desempenho está em qualquer lugar de O (1) a O (n).

Popularidade

Em geral, eu corri mais entre as árvores B. Os índices de bitmap também são outra opção para valores com baixa cardinalidade (pense em booleanos ou talvez sexo). Isso varia de acordo com o mecanismo do banco de dados e com que tipos de índice estão disponíveis.

NoSQL

Os bancos de dados NoSQL definitivamente suportam índices. A maioria suporta árvore B ou uma variação na árvore B. A maioria parece suportar índices de hash também.

Quais são as aventuras e desvantagens de ambas as soluções? A segunda solução não pode executar varreduras de intervalo. É ótimo para selecionar um único ID. Mas e se você quiser os IDs 3 a 8? Ele precisa 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ê obtém registros em páginas diferentes, exigindo que você bata no disco e leia seis páginas diferentes na memória.

Em uma estrutura de Árvore B, como a primeira situação seria implementada, os IDs seriam seqüenciais no disco e uma única página provavelmente conteria os IDs 3 a 8, aumentando a velocidade das varreduras de intervalo, tornando o acesso individual O (log n) .

Qual deles é mais popular nas implementações atuais de banco de dados? Talvez diferentes dbs usem abordagens diferentes? Eu não tenho uma grande experiência em muitos bancos de dados diferentes. Eu sei que o Sql Server usa B-Trees principalmente, mas o SQl 2014 tem alguns novos índices de hash que você pode usar em determinada tabela. Eu ouço muitos bancos de dados No Sql e bancos de dados de cache criados para recuperar registros individuais também usam índices de hash. Isso faz sentido para caches, pois você deseja o registro para o usuário A e não precisa de varreduras de intervalo.

Existe em dbs não SQL? Sim. Examinando rapidamente a documentação de criação de índice para o postgressql, vejo que ele suporta os índices Hash e B-Tree, além de alguns outros.