Exemplo de Espalhamento Extensível 1 Exemplo de Espalhamento Extensível Executar as operações abaixo: (Considerar buckets com 4 slots cada) Definição dos dados a processar Escondido pela moldura 2 Tom 2 001101101000 Registro 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Chave Ed Tom Sam Ann Kim Keli Mindy Mark Chris Laura Sue Jill Amy Don Dan Dick Sandra Ben Fred Bill Bob Andy Mary Jane Jack Joe Betty Assinatura 111010001010 001101101000 111100010100 010011010001 100111010100 011011011110 110111000101 110001011001 111001110011 001011010101 101110001100 111000110010 111000011101 010101110110 011010001110 100011011001 101100111001 010111011001 001101100011 000101101100 011001010111 001011001111 100111001011 101110110100 111000110110 001011011011 011001010100 Definição das transações Transações Incluir registros 1 a 4 Incluir registro 5 Incluir registro 6 Incluir registros 7 a 9 Incluir registro 10 Incluir registros 11 a 13 Incluir registros 14 a 17 Incluir registro 18 Excluir registros 12 e 16 3 Resultado da inclusão dos registros 1 a 4 Incluir d=0 0 1a4 1 Bucket 1 Nível 0 4 1 2 3 4 Ed Tom Sam Ann Transações Incluir registros 1 a 4 Incluir registro 5 Incluir registro 6 Incluir registros 7 a 9 Incluir registro 10 111010001010 Incluir registros 11 a 13 001101101000 Incluir registros 14 a 17 111100010100 010011010001 Incluir registro 18 Excluir registros 12 e 16 Resultado da inclusão do registro 5 Incluir d=1 0 1 5 1 2 Bucket 1 2 Tom 4 Ann 001101101000 010011010001 1 Ed 3 Sam 5 Kim 111010001010 111100010100 100111010100 Nível 1 Bucket 2 Nível 1 5 Transações Incluir registros 1 a 4 Incluir registro 5 Incluir registro 6 Incluir registros 7 a 9 Incluir registro 10 Incluir registros 11 a 13 Incluir registros 14 a 17 Incluir registro 18 Excluir registros 12 e 16 Resultado da inclusão do registro 6 Incluir d=1 0 1 6 1 2 Bucket 1 Nível 2 Tom 4 Ann 6 Keli 001101101000 010011010001 011011011110 1 Ed 3 Sam 5 Kim 111010001010 111100010100 100111010100 1 Bucket 2 6 Excluir registros 12 e 16 Incluir registro 18 Incluir registros 14 a 17 Incluir registros 11 a 13 Incluir registro 10 Incluir registros 7 a 9 Incluir registro 6 Incluir registro 5 Incluir registros 1 a 4 Transações Nível 1 Resultado da inclusão dos registros 7 a9 7 Incluir d=3 000 001 010 011 100 101 110 111 Excluir registros 12 e 16 Incluir registro 18 Incluir registros 14 a 17 Incluir registros 11 a 13 Incluir registro 10 Incluir registros 7 a 9 Incluir registro 6 Incluir registro 5 Incluir registros 1 a 4 Transações 7a9 1 1 1 1 2 2 3 4 Bucket 1 Nível 2 Tom 4 Ann 6 Keli 001101101000 010011010001 011011011110 5 Kim 100111010100 7 Mindy 8 Mark 110111000101 110001011001 1 Ed 3 Sam 9 Chris 111010001010 111100010100 111001110011 1 Bucket 2 Nível 2 Bucket 3 Nível 3 Bucket 4 Nível 3 Resultado da inclusão do registro 10 Excluir registros 12 e 16 10 Incluir d=3 000 001 010 011 100 101 110 111 8 Incluir registro 18 Incluir registros 14 a 17 Incluir registros 11 a 13 Incluir registro 10 Incluir registros 7 a 9 Incluir registro 6 Incluir registro 5 Incluir registros 1 a 4 Transações 1 1 1 1 2 2 3 4 Bucket 1 Nível 1 Bucket 2 4 6 10 Tom Ann Keli Laura 001101101000 010011010001 011011011110 001011010101 5 Kim 100111010100 7 Mindy 8 Mark 110111000101 110001011001 1 Ed 3 Sam 9 Chris 111010001010 111100010100 111001110011 2 Nível 2 Bucket 3 Nível 3 Bucket 4 Nível 3 Incluir d=4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 11 a 13 1 1 1 1 1 1 1 1 2 2 2 2 3 3 4 5 Resultado da inclusão dos Excluir registros 12 e 16 registro 18 registros Incluir Incluir registros 14 a 17 registros 11 a 13 11 a 13 Incluir Incluir registro 10 9 Incluir registros 7 Incluir registro Incluir registro Incluir registros 1 Transações a9 6 5 a4 Bucket 1 2 4 6 10 2 5 Kim 11 Sue 1 Nível Bucket Tom Ann Keli Laura 001101101000 010011010001 011011011110 001011010101 100111010100 101110001100 Nível 2 Bucket 3 7 Mindy 8 Mark 110111000101 110001011001 Nível 3 Bucket 4 Nível 4 Bucket 1 9 12 13 Ed Chris Jill Amy 3 Sam 5 Nível 4 111010001010 111001110011 111000110010 111000011101 111100010100 Incluir d=4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Resultado da inclusão dos registros 14 Excluir registros 12 e 16 Incluir registro 18 a 17 Incluir registros 14 a 17 10 Incluir registros 11 a 13 Incluir registro 10 Incluir registros 7 a 9 Incluir registro 6 Incluir registro 5 Incluir registros 1 a 4 Transações 14 a 17 1 1 1 1 6 6 6 6 2 2 2 2 3 3 4 5 Bucket 1 2 Tom 10 Laura 001101101000 001011010101 4 6 14 15 Ann Keli Don Dan 010011010001 011011011110 010101110110 011010001110 5 11 16 17 Kim Sue Dick Sandra 100111010100 101110001100 100011011001 101100111001 Nível 2 Bucket 6 Nível 2 Bucket 2 Nível 2 Bucket 3 7 Mindy 8 Mark 110111000101 110001011001 Nível 3 Bucket 4 Nível 4 Bucket 1 9 12 13 Ed Chris Jill Amy 3 Sam 5 Nível 4 111010001010 111001110011 111000110010 111000011101 111100010100 Incluir d=4 Resultado da inclusão Excluir registros Incluir registro Incluir registros do Incluir registros registro registro Incluir Incluir registros Incluir registro 18 Incluir registro 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 12 e 16 18 14 a 17 11 a 13 10 7a9 6 5 Incluir registros 1a4 Transações 11 18 1 1 1 1 6 6 7 7 2 2 2 2 3 3 4 5 Bucket 1 2 Tom 10 Laura 001101101000 001011010101 4 Ann 14 Don 18 Ben 010011010001 010101110110 010111011001 6 Keli 15 Dan 011011011110 011010001110 5 11 16 17 100111010100 101110001100 100011011001 101100111001 Nível 2 Bucket 6 Nível 3 Bucket 7 Nível 3 Bucket 2 Nível 2 Bucket 3 Kim Sue Dick Sandra 7 Mindy 8 Mark 110111000101 110001011001 Nível 3 Bucket 4 Nível 4 Bucket 1 9 12 13 Ed Chris Jill Amy 3 Sam 5 Nível 4 111010001010 111001110011 111000110010 111000011101 111100010100 Excluir d=4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Resultado da exclusão dos registros registros Excluir Incluir registro Incluir registros 12 e 16 Incluir registros Diretório antes da exclusão Diretório depois da exclusão 12 12 e 16 d=3 1 1 1 1 6 6 7 7 2 2 2 2 3 3 4 5 Incluir registro Incluir registros Incluir registro Incluir registro Incluir registros Transações 000 001 010 011 100 101 110 111 1 1 6 7 2 2 3 4 Bucket 1 001101101000 001011010101 4 Ann 14 Don 18 Ben 010011010001 010101110110 010111011001 6 Keli 15 Dan 011011011110 011010001110 5 Kim 11 Sue 17 Sandra 100111010100 101110001100 101100111001 7 Mindy 8 Mark 110111000101 110001011001 Nível 2 Bucket 6 Nível 3 Bucket 7 Nível 3 Bucket 2 12 e 16 18 14 a 17 11 a 13 10 7a9 6 5 1a4 2 Tom 10 Laura Nível 2 Bucket 3 Nível 3 Bucket 4 Nível 3 1 9 13 3 Ed Chris Amy Sam 111010001010 111001110011 111000011101 111100010100
Download
