Wondershare EdrawMind
Galeria de mapas mentais Estrutura de Dados Capítulo 7 - Pesquisa
- 9
Estrutura de Dados Capítulo 7 - Pesquisa
Capítulo 7 de "Estrutura de Dados" - Pesquisa de conhecimento, incluindo conceitos básicos de pesquisa, pesquisa sequencial e pesquisa binária, pesquisa em árvore, tabela hash, árvore B e árvore B, etc.
Editado em 2022-11-23 16:07:51
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Estrutura de Dados Capítulo 7 - Pesquisa
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
- Recomendado para você
- Descrição
Encontrar
Conceitos básicos de pesquisa
1) Encontre
O processo de encontrar elementos de dados que atendam a certas condições em uma coleta de dados
2) Tabela de pesquisa (estrutura de pesquisa)
Coleta de dados usada para pesquisa
tabela de pesquisa estática
Usado apenas para consultas
tabela de pesquisa dinâmica
Suporta inserção e exclusão dinâmica
3) Palavras-chave
O valor de um item de dados em um elemento de dados que identifica exclusivamente o elemento
4) Duração média da pesquisa
n: comprimento da tabela de pesquisa
Pi: A probabilidade de encontrar o i-ésimo elemento (geralmente 1/n)
Ci: o número de comparações necessárias para encontrar o i-ésimo elemento
Pesquisa sequencial e pesquisa binária
pesquisa sequencial
Pesquisa sequencial de tabelas lineares gerais
Encontre o comprimento médio de sucesso: (n 1)/2
Duração média das falhas de pesquisa: n 1
Pesquisa sequencial em lista ordenada
Encontre o comprimento médio de sucesso: (n 1)/2
Duração média da pesquisa com falha: n/2 n/(n 1)
Pesquisa pela metade (dois pontos)
Ideia básica
Aplicável apenas a listas sequenciais ordenadas, compare a chave com o elemento de posição intermediária e, em seguida, compare recursivamente o elemento de posição intermediária na primeira metade ou na segunda metade de acordo com o tamanho até que a pesquisa seja bem-sucedida ou falhe.
Implementar código
árvore de decisão
Usado para descrever o processo de meia pesquisa
Altura máxima do galho
Como a árvore de decisão é uma árvore binária balanceada, a diferença máxima de altura entre os galhos das árvores é 1, ou seja, o número máximo de comparações - o número mínimo de comparações = 1
A árvore de decisão também é uma árvore de classificação binária (ou seja, palavras-chave da subárvore esquerda <nó raiz <subárvore direita ou vice-versa)
complexidade de tempo:
Bloquear pesquisa
Ideia básica
Também conhecida como pesquisa de sequência de índice. Divida a tabela de pesquisa em vários blocos. As palavras-chave do bloco anterior são menores que as do bloco seguinte, mas os elementos do bloco podem ser desordenados. Cada item indica a palavra-chave máxima de cada bloco e o endereço. do primeiro elemento. A tabela de índice é organizada por palavras-chave em ordem.
Ao pesquisar, primeiro determine o bloco onde o registro a ser pesquisado está localizado na tabela de índice (use a tabela de índice sequencial ou de meia pesquisa e depois pesquise sequencialmente dentro do bloco);
Comprimento médio da pesquisa = pesquisa de índice na pesquisa de bloco
Todas as pesquisas em ordem
Divida a tabela de pesquisa de comprimento n em b blocos, cada bloco possui s registros.
A tabela de índice usa meia pesquisa e pesquisa sequencial dentro do bloco.
pesquisa de árvore
Árvore de classificação binária (BST)
definição
Uma árvore de classificação binária (também chamada de árvore de pesquisa binária) é uma árvore vazia ou uma árvore binária com as seguintes propriedades:
1) Se a subárvore esquerda não estiver vazia, os valores de todos os nós da subárvore esquerda serão menores que o valor do nó raiz.
2) Se a subárvore direita não estiver vazia, os valores de todos os nós da subárvore direita serão maiores que o valor do nó raiz.
3) As subárvores esquerda e direita também são uma árvore de classificação binária, respectivamente.
Execute uma travessia em ordem em uma árvore binária classificada para obter uma sequência ordenada crescente.
Encontrar
inserir
1) Se a palavra-chave k for menor que o valor do nó raiz, insira-a na subárvore esquerda, caso contrário, insira-a na subárvore direita;
2) O nó inserido deve ser um nó folha recém-adicionado e o filho esquerdo ou direito do último nó visitado no caminho de pesquisa quando a pesquisa falha.
3) Exclua e insira o mesmo nó na classificação binária. Se o nó for originalmente um nó folha, as árvores binárias anteriores e subsequentes permanecerão inalteradas e vice-versa. Para uma árvore binária balanceada, não importa se o nó original excluído é um. nó folha ou não, nós, AVL antes e depois podem mudar (ou não)
estrutura
Processo de construção
algoritmo
excluir
①Se o nó excluído for um nó folha, basta excluí-lo diretamente
②Se o nó excluído z tiver apenas uma subárvore esquerda ou subárvore direita, faça com que sua subárvore se torne a subárvore do nó pai de z
③Se z tiver duas subárvores, esquerda e direita, deixe seu sucessor direto (calculado de acordo com a sequência em ordem) ou antecessor direto substituir z e, em seguida, exclua o nó sucessor para converter para a situação anterior
análise de eficiência
1) A diferença de altura entre as subárvores esquerda e direita não excede 1, ou seja, uma árvore binária balanceada
Duração média da pesquisa:
2) Uma única árvore com apenas filho direito (esquerdo)
Duração média da pesquisa:
Comparação com pesquisa binária
1) O desempenho da pesquisa de uma árvore de classificação binária está relacionado à ordem de entrada dos dados. Somente na melhor das hipóteses, o desempenho da pesquisa é o mesmo da pesquisa binária.
2) Em termos de manutenção da ordem da tabela, uma árvore binária não precisa mover nós, ela só precisa modificar o ponteiro para completar as operações de inserção e exclusão. A complexidade do tempo é O (log2n), enquanto a pesquisa binária requer. O(n); quando existe Quando a tabela de sequência é uma tabela de pesquisa estática, é apropriado usar a tabela de sequência e a pesquisa binária. Quando é dinâmica, é apropriado usar uma árvore de classificação binária como estrutura lógica.
árvore binária balanceada
definição
Defina a diferença de altura entre as subárvores esquerda e direita de um nó como o fator de equilíbrio (alta esquerda - alta direita), então o fator de equilíbrio de um nó de árvore binária balanceado só pode ser 0, 1, -1, ou seja, a altura diferença entre as subárvores esquerda e direita de qualquer nó não superior a 1
inserir
1) Inserção de nós semelhantes à árvore de classificação binária
2) Assim que o nó inserido destruir o equilíbrio, encontre a menor subárvore desequilibrada e gire-a.
①LL rotação balanceada (rotação única direita)
Insira um novo nó na subárvore esquerda do filho esquerdo do nó A; ele precisa ser girado para a direita, para se tornar o nó raiz da subárvore direita de B. e a árvore filha direita original de B como a subárvore esquerda de A
②RR rotação equilibrada (rotação única esquerda)
Insira um novo nó na subárvore direita do filho direito do nó A; ele precisa ser girado para a esquerda, B para se tornar o nó raiz da subárvore esquerda de B. A subárvore esquerda original de A serve como a subárvore direita de A
③Rotação balanceada LR (rotação dupla primeiro para a esquerda e depois para a direita)
Para inserir um novo nó na subárvore direita do filho esquerdo de A, você precisa primeiro girar o nó raiz C da subárvore direita do filho esquerdo B de A para a esquerda e para cima até a posição de B e, em seguida, girar C para a direita e até a posição de A.
④RL rotação equilibrada (rotação dupla para a esquerda em sucessão)
excluir
1) Use o método da árvore de classificação binária para realizar a operação de exclusão no nó w.
2) A partir do nó w, rastreie para cima para encontrar o primeiro nó desequilibrado z (ou seja, a menor subárvore desequilibrada y é o nó filho com a altura mais alta do nó z; x é a altura do nó y O nó filho mais alto);
3) Em seguida, equilibre a subárvore com z como raiz, onde existem 4 posições possíveis de x, y e z:
① y é o filho esquerdo de z, x é o filho esquerdo de y (LL, rotação única à direita);
②y é o filho esquerdo de z e x é o filho direito de y (LR, rotação dupla primeiro para a esquerda e depois para a direita);
③y é o filho direito de z, x é o filho direito de y (RR, rotação única para a esquerda);
④y é o filho direito de z, x é o filho esquerdo de y (RL, rotação dupla primeiro para a direita e depois para a esquerda)
ah
Encontrar
O processo de pesquisa é o mesmo de uma árvore de classificação binária e o comprimento médio da pesquisa é O (log2n)
Número de nós
nh é o número mínimo de nós de uma árvore binária balanceada com altura h
árvore vermelha preta
definição
Uma árvore rubro-preta é uma árvore binária classificada que satisfaz as seguintes propriedades rubro-pretas:
①Cada nó é vermelho ou preto.
②O nó raiz é preto.
③Os nós folha (nós externos fictícios, nós NULL) são todos pretos.
④ Não há dois nós vermelhos adjacentes (ou seja, o nó pai e o nó filho do nó vermelho são ambos pretos).
⑤ Para cada nó, o caminho simples do nó para qualquer nó folha contém o mesmo número de nós pretos.
O número total de nós pretos em qualquer caminho simples de um nó (excluindo este nó) até um nó folha é chamado de altura preta do nó (registrada como bh). A altura negra
natureza
1. O caminho mais longo do nó raiz ao nó folha não é mais do que o dobro do caminho mais curto
2. Altura de uma árvore rubro-negra com n nós internos
inserir
Insira usando o método de inserção de árvore de pesquisa binária e pinte o novo nó z em vermelho
Se z for o nó raiz, pinte-o de preto e termine
Se z não for o nó raiz
Se o nó pai de z for preto, nenhum ajuste será necessário
Se o nó pai de z for vermelho
①O nó tio y de z é preto e z é um filho certo
LR (se z.p for o filho certo, é RL), gire para a esquerda uma vez e torne-se ②
②O nó tio y de z é preto e z é um filho esquerdo
LL (ou RR se z.p for o filho certo), gire para a direita uma vez e troque z.p e z.p.p e cores
③Se o nó tio y de x for vermelho
Pinte z.p.e y de preto, pinte z.p.p de vermelho e, em seguida, use z.p.p como o novo nó z para repetir o ciclo até que ①, ② ou z seja o nó raiz.
excluir
1) O processo de exclusão primeiro executa o método de exclusão da árvore de pesquisa binária. Se o nó a ser excluído tiver dois filhos, ele será trocado pelo nó sucessor na ordem (ou seja, o menor nó na subárvore direita), e então convertido para exclusão. Este nó sucessor tem no máximo um filho, então é convertido para a situação em que o nó a ser excluído não tem filhos ou tem apenas um filho.
2) Se o nó a ser excluído tiver apenas um filho direito ou um filho esquerdo, pode-se observar pelas suas propriedades que deve ser um nó preto e seu filho deve ser um nó vermelho.
3) Se o nó a ser excluído não tiver filhos
①Se o nó estiver vermelho, exclua-o diretamente
② Se o nó a ser excluído não tiver filhos e for vermelho, registre x como o nó usado para substituir y (x é um nó nulo preto para manter a altura do preto inalterada, x é posicionado como um nó preto duplo, e precisa ser Reverter para o nó normal
1. O nó irmão w de x é vermelho
Neste momento, w deve ter filhos pretos esquerdo e direito e nós pais trocarem as cores de w e x.p e, em seguida, girar x.p para a esquerda, convertendo a situação 1 em 2, 3 e 4;
2. O nó irmão w de x é preto, o filho esquerdo de w é vermelho e o filho direito é preto.
RL, ou seja, o nó vermelho é o filho esquerdo do filho direito de seu nó pai. Troque as cores de w e seu filho esquerdo, gire w para a direita e converta para o caso 3
3. O nó irmão w de x é preto e o filho direito de w é vermelho.
RR. Troque as cores de w e x.p, pinte o filho direito de w de preto e gire x.p para a esquerda para mudar x de volta para preto único e termine
4. O nó irmão w de x é preto e os dois nós filhos de w são ambos pretos.
Remova uma camada de preto de x e w (ou seja, w fica vermelho). Como compensação, adicione uma camada adicional de preto a x.p para manter a altura local do preto.
Se x.p for originalmente vermelho, mude para preto e termine
Se x.p for originalmente preto, use-o como um novo nó x para entrar no loop
tabela hash
conceito básico
Função hash: uma função que mapeia uma palavra-chave em uma tabela de pesquisa para o endereço correspondente à palavra-chave, registrado como Hash(key)=Addr (o endereço aqui pode ser um subscrito de array, índice ou endereço de memória, etc.).
A função hash pode mapear duas ou mais palavras-chave diferentes para o mesmo endereço, o que é chamado de colisão. Essas palavras-chave diferentes que colidem são chamadas de sinônimos. Por um lado, uma função hash bem projetada deve minimizar tais conflitos; por outro lado, uma vez que tais conflitos são sempre inevitáveis, deve ser projetado um método para lidar com eles;
Tabela hash: uma estrutura de dados que é acessada diretamente com base em palavras-chave. Em outras palavras, a tabela hash estabelece um relacionamento de mapeamento direto entre palavras-chave e endereços de armazenamento.
Como construir uma função hash
Exigir
1) O domínio da função hash deve incluir todas as palavras-chave que precisam ser armazenadas, e o intervalo do domínio de valor depende do tamanho da tabela hash ou do intervalo de endereços.
2) Os endereços calculados pela função hash devem ser distribuídos uniformemente em todo o espaço de endereçamento com igual probabilidade, reduzindo assim a ocorrência de conflitos.
3) A função hash deve ser o mais simples possível e pode calcular o endereço hash correspondente a qualquer palavra-chave em um curto espaço de tempo.
Funções hash comumente usadas
método de endereçamento direto
Ideia básica
Tome diretamente o valor de uma função linear da palavra-chave como o endereço hash
Função hash
H(chave)=chave ou H(chave)=a×chave b
Características
É simples e não causa conflitos, sendo adequado para distribuição contínua de palavras-chave, caso contrário desperdiçará espaço de armazenamento.
método de divisão deixando resto
Ideia básica
Deixe o comprimento da tabela hash ser m, pegue um número primo p que seja menor e mais próximo ou igual a m e use a fórmula para converter a palavra-chave em um endereço hash
Função hash
H(chave)=chave%p
Características
O método mais comum e simples
análise digital
Ideia básica
Para r dígitos de um número de base r, selecione um número de bits com uma distribuição relativamente uniforme de dígitos como endereço hash.
Características
Adequado para conjuntos de palavras-chave conhecidas. Se as palavras-chave forem alteradas, uma nova função hash precisará ser reconstruída.
Método Quadrado-Médio
Ideia básica
Pegue os dígitos do meio do valor quadrado da palavra-chave como o endereço hash
Características
Os valores de cada bit usado apenas para palavras-chave não são uniformes o suficiente ou são menores que o número de bits necessários para o endereço hash.
Como lidar com conflitos
método de endereçamento aberto
definição
O endereço livre onde uma nova entrada pode ser armazenada está aberto tanto para suas entradas sinônimas quanto para suas entradas não-sinônimas.
fórmula de recursão
Hi representa o endereço hash obtido pela i-ésima detecção no processamento de conflitos, m representa o comprimento da tabela hash e di é a sequência de incremento.
sequência incremental
Método de detecção linear
Ideia básica
di=0, 1,...,m-1, ou seja, quando ocorrer um conflito, verifique a próxima unidade da tabela sequencialmente até que uma unidade livre seja encontrada ou toda a tabela seja pesquisada.
Características
É fácil fazer com que um grande número de elementos se "agreguem" em endereços hash adjacentes, o que reduz bastante a eficiência da pesquisa.
Com a sondagem linear, podem ocorrer conflitos mesmo que não sejam sinônimos
método de detecção quadrada
Ideia básica
di=0^2, 1^2, -1^2...,k^2,-k^2, onde k≤m/2, o comprimento da tabela hash m deve ser um número primo que pode ser expresso como 4K 3, também conhecido como método de detecção secundária
Características
Evita problemas de “empilhamento”, mas não consegue detectar todas as células na tabela hash (mas pode detectar pelo menos metade das células)
hash duplo
Ideia básica
di=Hash2(chave), ou seja, duas funções hash são usadas Quando o endereço obtido pela primeira função hash H(chave) entra em conflito, a segunda função hash Hash2(chave) é usada para calcular o incremento de endereço.
Função hash
método de sequência pseudoaleatória
di = sequência numérica pseudo-aleatória
Método Zipper (encadeamento)
Armazene todos os sinônimos em uma lista encadeada linear identificada exclusivamente por seu endereço hash adequado para situações onde inserções e exclusões são frequentes;
Pesquisa de hash e análise de desempenho
Processo de pesquisa
① Verifique se há registro no endereço de Addr na tabela de consulta. Se não houver registro, retorne a falha da pesquisa; se houver registro, compare-o com o valor da chave. sinalizador de sucesso, caso contrário, execute a etapa ②.
② Use o método de tratamento de conflitos fornecido para calcular o "próximo endereço hash", defina Addr para este endereço e vá para a etapa ①.
Comprimento médio de pesquisa ASL = 2,5
Classificação
Pesquisa bem-sucedida
Encontre o comprimento de cada elemento conhecido
O número de comparações bem-sucedidas = o número de conflitos 1
Falha na pesquisa
O comprimento de pesquisa de cada posição de pesquisa determinado pela função hash
Encontre fatores que afetam a eficiência
Função hash
Como lidar com conflitos
Fator de preenchimento α = número de registros na tabela n/comprimento da tabela hash m
Árvore B e árvore B
Árvore B e suas operações básicas
definição
Árvore B, também conhecida como árvore de pesquisa balanceada multidirecional, o número máximo de filhos de todos os seus nós é chamado de ordem da árvore B, denotada como m. Uma árvore B de ordem m é uma árvore vazia ou. uma árvore que satisfaz as seguintes propriedades da árvore m-ária:
1) Cada nó da árvore possui no máximo m subárvores, ou seja, contém no máximo m-1 palavras-chave
2) Se o nó raiz não for um nó terminal, existem pelo menos duas subárvores
3) Todos os nós não-folha, exceto o nó raiz, possuem pelo menos subárvores "m/2], ou seja, contêm pelo menos palavras-chave "m/2]-1.
4) A estrutura de todos os nós não-folha é a seguinte:
Ki é a palavra-chave do nó, classificada em ordem crescente
Pi é um ponteiro para o nó raiz da subárvore. As chaves de todos os nós da subárvore apontadas por Pi-1 são menores que Ki.
n é o número de palavras-chave
5) Todos os nós folha aparecem no mesmo nível e não carregam nenhuma informação (ou seja, nós externos, os ponteiros para esses nós estão vazios)
Propriedades (assumindo m=5)
1) O número de filhos de um nó é igual ao número de palavras-chave no nó mais 1.
2) Se o nó raiz não tiver palavras-chave, não haverá subárvores, e a árvore B estará vazia neste momento, se o nó raiz tiver palavras-chave, suas subárvores deverão ser maiores ou iguais a dois, pois o número de subárvores; é igual ao número de palavras-chave mais 1.
3) Todos os nós não terminais, exceto o nó raiz, têm pelo menos "m/2]-1=3 subárvores e no máximo 5 subárvores (ou seja, no máximo 4 palavras-chave).
4) As palavras-chave no nó estão em ordem crescente da esquerda para a direita. Existem ponteiros para a subárvore em ambos os lados da palavra-chave. Todas as palavras-chave da subárvore apontadas pelo ponteiro esquerdo são menores que a palavra-chave apontada. pelo ponteiro direito é menor que a palavra-chave. Todas as palavras-chave são maiores que esta palavra-chave.
5) Todos os nós folha estão no 4º nível, representando o local onde a busca falhou.
A altura da árvore B (número de acessos ao disco)
1) Cada nó da árvore B tem no máximo m subárvores e m-1 palavras-chave. Portanto, o número de palavras-chave em uma árvore B de ordem m com altura h deve satisfazer n≤(m-1)(1). m m^2 …… m^(h-1))=m^h-1
2) O nó raiz tem pelo menos 2 subárvores, o nó não raiz tem pelo menos palavras-chave "m/2]-1 e o primeiro nível h tem pelo menos 2("m/2])^(h-1) pontos de nós, e o número de nós folha é n 1
Pesquisa de árvore B
①Encontre nós na árvore B
Realizado no disco, encontre o nó correspondente com base na comparação de palavras-chave
Se um nó folha for encontrado (o ponteiro correspondente é um ponteiro nulo), significa que não há palavra-chave correspondente na árvore e a pesquisa falha.
②Encontre palavras-chave em nós
Realizado na memória, usando métodos de pesquisa sequencial ou binária dentro do nó
Inserção na árvore B
1) Se o número de palavras-chave do nó após a inserção for menor que m, você pode inseri-lo diretamente
2) Caso contrário, pegue o nó na posição intermediária ("m/2]) e insira-o no nó pai do nó original, e o nó original será dividido em duas partes; se isso causar o número de palavras-chave do nó original nó pai estourar, continue Split até atingir o nó raiz, o que por sua vez faz com que a altura da árvore B seja aumentada em 1
Exclusão da árvore B
1) Se a palavra-chave excluída k não estiver no nó terminal (o nó não folha de nível mais baixo), substitua k pelo antecessor (ou sucessor) de k k' e, em seguida, exclua k' no nó correspondente (k' deve ser eliminado em um nó terminal)
2) Se a palavra-chave excluída k estiver no nó terminal
①Exclua palavras-chave diretamente. A condição é que o número de palavras-chave no nó seja ≥ "m/2]. Após a exclusão da palavra-chave, ela ainda atende à definição de árvore B.
②Os irmãos podem pedir emprestado o suficiente. Se o número de palavras-chave do nó = "m/2]-1, e o número de palavras-chave do nó irmão ≥ "m/2], então ajuste o nó, o nó irmão direito (esquerdo) e seu nó pai (pai método de transposição -son) para alcançar um novo equilíbrio
③Não há irmãos suficientes para pedir emprestado. Se o número de palavras-chave do nó e de seus nós irmãos esquerdo e direito forem ambos "m/2]-1, exclua as palavras-chave e mescle-as com as palavras-chave do nó irmão esquerdo (direito) e do nó pai.
Conceitos básicos de árvores B
A árvore B é uma árvore deformada da árvore B que atende às seguintes condições:
1) Cada nó de ramificação possui no máximo m subárvores (nós filhos).
2) O nó raiz não folha tem pelo menos duas subárvores, e cada outro nó de ramificação tem pelo menos "m/2] subárvores.
3) O número de subárvores de um nó é igual ao número de palavras-chave.
4) Todos os nós folha contêm todas as palavras-chave e ponteiros para os registros correspondentes. As palavras-chave são organizadas em ordem de tamanho nos nós folha, e os nós folha adjacentes são vinculados uns aos outros em ordem de tamanho.
5) Todos os nós de ramificação (índices que podem ser considerados índices) contêm apenas o valor máximo da palavra-chave em cada um de seus nós filhos (ou seja, o bloco de índice do próximo nível) e os ponteiros para seus nós filhos.
A diferença entre árvore B e árvore B:
1) Na árvore B, um nó com n palavras-chave contém apenas n subárvores, ou seja, cada palavra-chave corresponde a uma subárvore enquanto na árvore B, um nó com n palavras-chave contém n 1 subárvores;
2) Na árvore B, o intervalo do número n de palavras-chave para cada nó (nó interno não raiz) é "m/2]<n<m (nó raiz: 2<n<m); em B Na árvore árvore, o intervalo do número n de palavras-chave para cada nó (nó interno não raiz) é "m/2]-1<n<m-1 (nó raiz: 1≤n≤m-1).
3) Na árvore B, os nós folha contêm informações e todos os nós não folha servem apenas como índices. Cada item de índice em um nó não folha contém apenas a palavra-chave máxima da subárvore correspondente e um ponteiro para a subárvore. o endereço de armazenamento do registro correspondente a esta palavra-chave não está incluído.
4) Na árvore B, os nós folha contêm todas as palavras-chave, ou seja, as palavras-chave que aparecem em nós não-folha também aparecerão em nós folha na árvore B, nós folha (o nó interno mais externo) e as palavras-chave contidas em; outros nós não são repetidos.
Encontrar
① Existem dois ponteiros principais na árvore B: um aponta para o nó raiz e o outro aponta para o nó folha com a menor palavra-chave, portanto, duas operações de pesquisa podem ser realizadas na árvore B: uma é uma pesquisa sequencial começando; da menor palavra-chave e a outra é A primeira é uma pesquisa multidirecional começando no nó raiz
②Ao pesquisar na árvore B, não importa se foi bem-sucedido ou não, cada pesquisa é um caminho do nó raiz ao nó folha.