Para possibilitar acessos aleatórios rápidos aos registros de um arquivo, uma estrutura de índice pode ser utilizada. Em um arquivo organizado com índice seqüencial, o desempenho dos acessos ao arquivo tipicamente piora na medida em que o arquivo cresce. Para evitar essa degradação, há SGBDs que usam uma estrutura árvore-B+ para implementar índices de múltiplos níveis.