Que tipo de dado ou estrutura de dados é usada para organizar os registros de índice numa base de dados ou motor de busca?

Para organizar registos indexados numa base de dados ou motor de busca, geralmente são utilizadas estruturas de dados baseadas em árvores, sendo as mais comuns as árvores B e B+. Estas estruturas permitem realizar operações de busca, inserção e eliminação de forma eficiente com complexidade logarítmica.

Nos motores de busca, é frequentemente utilizado um índice invertido, que armazena para cada termo uma lista de documentos onde ele aparece. Para implementar essas listas, utilizam-se estruturas de dados otimizadas para acesso rápido e compressão, como tabelas de hash ou árvores.

Exemplo: árvore B para indexar chaves numa base de dados.

// Pseudocódigo para representar uma árvore B
class BTreeNode {
    public $keys = [];
    public $children = [];
    public $leaf = true;

    // métodos de inserção, busca e remoção
}

// O índice na base de dados é construído com base nestes nós para uma busca rápida por chave

Assim, o tipo de dado chave para os registos indexados é uma árvore balanceada, que garante uma busca e atualização eficientes.