1. Fichero secuencial frente a índice
Medio · Sistemas de Almacenamiento · apuntesdam.com/subject/bases-datos/topic/almacenamiento
¿Por qué una base de datos con índice encuentra un registro entre millones casi al instante? La entrada tiene registros «id nombre» en el orden en que están en el fichero (desordenados) y búsquedas «buscar id». El índice ya está construido: una lista ordenada de (id, posición). Para cada búsqueda cuenta las lecturas de la búsqueda secuencial en el fichero (se leen registros desde el principio hasta encontrarlo; si no está, todos) y las comparaciones de una búsqueda binaria en el índice (lo = 0, hi = n−1; mientras lo ≤ hi: mid = (lo+hi)//2, se cuenta una comparación y se mira si es el buscado, si es menor o si es mayor), más una lectura del registro si se encuentra. Muestra «buscar x: encontrado (nombre) · secuencial S lecturas · índice C comparaciones + 1 lectura» (o «no existe» y sin «+ 1 lectura»; en singular «1 lectura» y «1 comparación») y al final «Total secuencial: S lecturas · índice: I accesos · ahorro P %» con P = 100 − 100·I/S redondeado.
import sys registros = [] # (id, nombre) en el orden del fichero (sin ordenar)busquedas = []for linea in sys.stdin.read().splitlines(): p = linea.split() if not p: continue if p[0] == "buscar": busquedas.append(int(p[1])) else: registros.append((int(p[0]), p[1])) indice = sorted((r[0], pos) for pos, r in enumerate(registros)) # (id, posición en el fichero)# TODO: para cada búsqueda, contar lecturas secuenciales y comparaciones de la búsqueda binaria en el índiceEjemplo: 40 registros
Entrada
431 Ana0
254 Luis1
504 Eva2
766 Juan3
149 Marta4
174 Pablo5
940 Lucía6
648 Hugo7
196 Sara8
474 Iker9
696 Ana10
159 Luis11
619 Eva12
319 Juan13
138 Marta14
188 Pablo15
544 Lucía16
528 Hugo17
171 Sara18
346 Iker19
192 Ana20
664 Luis21
534 Eva22
160 Juan23
946 Marta24
679 Pablo25
226 Lucía26
328 Hugo27
745 Sara28
742 Iker29
163 Ana30
690 Luis31
699 Eva32
506 Juan33
150 Marta34
326 Pablo35
147 Lucía36
670 Hugo37
979 Sara38
236 Iker39
buscar 431
buscar 679
buscar 236
buscar 5
buscar 474Salida esperada
buscar 431: encontrado (Ana0) · secuencial 1 lectura · índice 1 comparación + 1 lectura
buscar 679: encontrado (Pablo25) · secuencial 26 lecturas · índice 5 comparaciones + 1 lectura
buscar 236: encontrado (Iker39) · secuencial 40 lecturas · índice 6 comparaciones + 1 lectura
buscar 5: no existe · secuencial 40 lecturas · índice 5 comparaciones
buscar 474: encontrado (Iker9) · secuencial 10 lecturas · índice 5 comparaciones + 1 lectura
Total secuencial: 117 lecturas · índice: 26 accesos · ahorro 78 %