Los discos magnéticos son los dispositivos de almacenamiento secundario más utilizados para almacenar los ficheros de una base de datos. Los datos se almacenan en sectores/bloques en el disco. El acceso a un sector/bloque es costoso debido al tiempo de búsqueda, el tiempo de rotación y el tiempo de transferencia del bloque.
Hay tres organizaciones primarias para los ficheros: desordenados, ordenados y dispersos. Los ficheros desordenados requieren una búsqueda lineal para localizar registros, pero la inserción de éstos es muy sencilla. La eliminación plantea problemas en el sentido de que se desperdicia espacio, recuperable mediante una reorganización del fichero.
Los ficheros ordenados reducen el tiempo requerido para leer registros en orden según el campo de ordenación. El tiempo necesario para buscar un registro cualquiera dado el valor de su campo de ordenación también se reduce, ya que se puede realizar una búsqueda binaria. Sin embargo, la necesidad de mantener los registros en orden hace muy costosa la inserción. Por esta razón, se puede utilizar un fichero de desborde no ordenado para reducir el coste de la inserción. Los registros de desborde se fusionan con el fichero de datos periódicamente.
La dispersión ofrece acceso muy rápido a un registro cualquiera dado el valor de su campo de dispersión. Las colisiones que causan desborde en los bloques se pueden resolver de varios modos, el más frecuente es el encadenamiento. El acceso a un registro a través de un campo que no es el campo de dispersión, es lento, y lo mismo sucede con el acceso secuencial a los registros a través de cualquier campo. Hay varias técnicas que permiten al fichero expandirse y contraerse dinámicamente: la dispersión dinámica, la extensible y la lineal.
El agrupamiento es otro modo de organizar los registros, cuyo resultado es un fichero ordenado de un modo especial. Mediante el agrupamiento se implementan físicamente las relaciones entre los registros de varios ficheros, almacenándolos consecutivos en el mismo fichero.
Los índices son estructuras de acceso adicionales con las que se mejora la eficiencia en la obtención de registros de un fichero de datos. Dichas estructuras de acceso pueden usarse junto con las organizaciones de ficheros vistas anteriormente.
Hay tres tipos de índices ordenados de un solo nivel: primarios, secundarios y de agrupamiento. Cada índice se basa en un campo del fichero. Los índices primarios y de agrupamiento se construyen según el campo de ordenamiento físico del fichero, en tanto que los índices secundarios se basan en campos que no son de ordenamiento. El campo de un índice primario debe ser además un campo con valores únicos (clave), cosa que no sucede con un índice de agrupamiento. Los índices de un solo nivel son ficheros ordenados, y se examinan mediante una búsqueda binaria. Se pueden construir índices de varios niveles (multinivel) para mejorar la eficiencia en las búsquedas.
Los árboles B y los árboles B+ son índices multinivel cuya estructura permite al índice expandirse y contraerse dinámicamente. Los nodos (bloques) de estas estructuras se mantienen ocupados entre el 50% y el 100% de su capacidad gracias a sus algoritmos de inserción y eliminación. Después de cierto tiempo, los nodos se estabilizan en un grado de ocupación medio del 69%, lo que deja espacio para hacer inserciones sin tener que reorganizar el índice con mucha frecuencia. En general, los árboles B+ pueden contener más entradas en sus nodos internos que los árboles B, por lo que es posible que un árbol B+ tenga menos niveles o incluya más entradas que el árbol B equivalente.
También es posible construir índices mediante estructuras de datos que utilizan la técnica de la dispersión.