La densidad: siempre un sitio nuevo entre otros dos

La cuarta exigencia de la lección anterior quedó enunciada y sin desarrollar, y es la que decide si todo el edificio se sostiene. Un espacio de posiciones no basta con que esté ordenado: tiene que ser denso, es decir, entre dos posiciones cualesquiera ha de existir siempre una tercera estrictamente intermedia, y esa operación debe poder repetirse sin límite porque nada impide que alguien escriba mil veces seguidas en el mismo punto de un párrafo. Los números reales cumplen esa propiedad por definición, y por eso todas las explicaciones informales del tema los usan. Los números que tu máquina sabe manipular no la cumplen en absoluto, y la distancia entre esas dos frases es el contenido entero de esta lección: qué pasa exactamente cuando el espacio se agota, y qué se construye en su lugar.

Qué pide exactamente la densidad

Un orden es denso cuando para todo par de elementos p y q con p menor que q existe un tercero r que cumple las dos desigualdades a la vez. Es una propiedad familiar: los racionales la tienen, los reales la tienen, los enteros no la tienen porque entre 4 y 5 no hay nada. Lo que rara vez se subraya, y aquí es lo decisivo, es que necesitamos algo más fuerte que la existencia matemática. Necesitamos una función constructiva que reciba los dos extremos y devuelva el intermedio, que se pueda ejecutar en cualquier réplica sin consultar a nadie, y que siga funcionando después de haberse aplicado un millón de veces sobre sus propios resultados.

Esa última cláusula es la que se olvida. Cualquier esquema aguanta las primeras inserciones; el problema aparece cuando alguien escribe un párrafo entero entre dos caracteres, porque cada carácter nuevo se inserta entre el anterior y el mismo tope, y la petición de intermedio se encadena consigo misma. Una implementación seria tiene que sobrevivir a esa cadena de longitud arbitraria, y ese es el escenario contra el que hay que probar cualquier idea antes de escribirla.

Las tres primeras tarjetas son cada vez más exigentes y las tres hacen falta. La primera la cumplen los racionales sobre el papel; la segunda excluye cualquier esquema que necesite un árbitro para asignar posiciones; y la tercera es la que descarta, sin excepción, a todos los tipos numéricos que tu máquina implementa de forma nativa. La cuarta tarjeta no es una propiedad sino el criterio de prueba, y conviene tratarla como tal: cualquier idea sobre identificadores de posición debe enfrentarse a ese escenario antes de que se escriba una línea de la implementación definitiva.

Por qué los números de máquina no valen

El primer intento de todo el mundo son los enteros, con la idea de dejar huecos: numerar de cien en cien y usar el punto medio. Funciona seis o siete veces y luego los extremos quedan adyacentes y no hay punto medio entero. El segundo intento son los flotantes de doble precisión, que parecen resolverlo porque siempre se puede promediar. La apariencia dura poco: un flotante tiene cincuenta y dos bits de mantisa, cada punto medio consume aproximadamente uno, y a la subdivisión número cincuenta y tantas el promedio de dos vecinos devuelve uno de los propios extremos.

// Cuantas subdivisiones aguanta un flotante antes de colapsar
let bajo = 0;
let alto = 1;
let pasos = 0;

while (true) {
  const medio = (bajo + alto) / 2;
  if (medio === bajo || medio === alto) break; // ya no hay nada en medio
  alto = medio; // insertamos siempre justo detras del anterior
  pasos++;
}

console.log(pasos); // del orden de 52: menos de una frase escrita del tiron

Cincuenta y dos pulsaciones es menos de una frase. Y el fallo no es un error que se pueda capturar y reintentar, porque cuando el punto medio coincide con un extremo, la nueva posición es igual a la de un elemento existente y el orden entre ambos queda indeterminado: dos réplicas pueden resolver el empate de maneras distintas y la convergencia se pierde en silencio. Es el peor tipo de fallo posible, porque no lanza ninguna excepción y solo se manifiesta como dos usuarios que ven textos diferentes.

flowchart TD
A[intervalo entre dos posiciones] --> B[calcular el punto medio]
B --> C{queda espacio en la mantisa}
C -- si --> D[nueva posicion valida]
D --> B
C -- no --> E[el medio coincide con un extremo]
E --> F[dos elementos con la misma posicion]
F --> G[el orden depende de la replica y se pierde la convergencia]
style D fill:#a6e3a1,color:#11111b
style G fill:#f38ba8,color:#11111b

La moraleja general vale para cualquier tipo numérico de anchura fija y conviene enunciarla así de rotunda: ningún tipo de tamaño acotado puede ser denso de forma ilimitada, porque un tipo de k bits tiene como mucho dos elevado a k valores distintos, y una sucesión de subdivisiones encadenadas los agota en k pasos. No es un defecto de los flotantes ni una limitación de la aritmética actual: es contar. Si quieres subdividir sin límite, el identificador tiene que poder crecer sin límite, y esa conclusión es forzosa antes de mirar ningún algoritmo.

Conviene además desactivar dos escapatorias que aparecen siempre en esta conversación. La primera es usar enteros de precisión arbitraria y multiplicar por mil cada nivel para dejar hueco: eso funciona, pero un entero de precisión arbitraria es precisamente un valor de longitud variable, así que no has evitado el crecimiento, lo has disfrazado de número. La segunda es renumerar la lista entera cada cierto tiempo para recuperar espacio, que es lo que hace cualquier base de datos con un campo de orden. Renumerar exige que todas las réplicas acuerden la nueva numeración, es decir, exige coordinación, y coordinar es exactamente lo que esta arquitectura no puede presuponer: una réplica desconectada seguiría insertando contra la numeración vieja y aterrizaría en cualquier sitio.

Cómo se fabrica densidad de verdad

La construcción que funciona abandona el número de anchura fija y usa secuencias de longitud variable comparadas lexicográficamente, que es lo mismo que hace un diccionario. Entre las palabras ca y cb no hay nada de dos letras, pero sí hay infinitas de tres o más: caa, cab, caz, caaa. Alargar la secuencia crea espacio nuevo donde antes no lo había, y ese espacio nunca se acaba porque la longitud no tiene tope.

// Identificador denso: lista de digitos comparada lexicograficamente
const BASE = 256;

function entre(izq, der) {
  const salida = [];
  for (let i = 0; ; i++) {
    const a = izq[i] ?? 0;
    const b = der[i] ?? BASE;
    if (b - a > 1) {
      salida.push(a + 1 + Math.floor(Math.random() * (b - a - 1)));
      return salida; // cabe un digito: hemos terminado
    }
    salida.push(a); // no cabe: copiamos y alargamos un nivel mas
  }
}

entre([1], [2]);        // por ejemplo [1, 137]: la longitud crece un nivel
entre([1, 137], [2]);   // [1, 200] o similar: aun cabe sin alargar

Repara en la propiedad que hace correcto el algoritmo: el bucle no puede quedarse sin salida, porque en el peor caso copia el prefijo del extremo izquierdo y añade un nivel más, donde el extremo derecho pasa a ser el tope de la base y siempre hay sitio. La contrapartida es igual de clara y define el resto del nivel: el identificador se alarga cada vez que el hueco estaba apretado, de modo que escribir seguido en el mismo punto produce identificadores cada vez más largos, y esa longitud es memoria que hay que guardar, ancho de banda que hay que gastar y tiempo de comparación que hay que pagar.

Cuánto crecen depende de decisiones concretas y aquí es donde los algoritmos publicados se diferencian entre sí. La base influye, porque una base grande retrasa el alargamiento a costa de más bits por nivel. La estrategia de elección dentro del hueco influye mucho más de lo que parece: elegir siempre el extremo bajo hace que escribir hacia delante consuma un nivel por carácter, mientras que elegir con un sesgo adecuado según la dirección de la escritura mantiene la longitud casi constante en el caso común. Y hay una tercera decisión, la de asignar huecos de tamaño creciente por nivel, que es el corazón de los esquemas de asignación adaptativa.

El caso patológico que conviene tener siempre en la cabeza es el opuesto al de escribir hacia delante, y aparece en una interfaz cotidiana: la lista donde todo el mundo añade por arriba. Cada inserción nueva pide un identificador entre el principio absoluto y el elemento que estaba primero, de modo que el intervalo disponible se estrecha en la misma dirección una y otra vez y la longitud crece de forma lineal con el número de elementos. Una lista de tareas con miles de altas por arriba puede acabar con identificadores de cientos de dígitos, y el síntoma no es un fallo sino una lentitud progresiva que nadie sabe atribuir. Por eso las implementaciones que se toman esto en serio detectan la dirección de la escritura y sesgan la elección en consecuencia.

La densidad no basta sola

Hay que cerrar con una advertencia contra la lectura simplificada, porque el orden denso resuelve una condición necesaria y no todas. Un espacio de posiciones puede ser denso y aun así producir listas incorrectas si le faltan las otras tres exigencias. Sin unicidad, dos elementos concurrentes pueden caer en el mismo punto y el orden queda a merced de cómo desempate cada réplica. Sin inmutabilidad, la densidad no sirve de nada porque las posiciones vuelven a ser negociables. Y sin un criterio de desempate determinista y compartido, las dos réplicas ordenan el empate de forma distinta y divergen.

Queda además un requisito que la densidad ni siquiera roza y que la lección siguiente pone en el centro. Que exista un identificador intermedio no dice nada sobre si el elemento acabará donde el usuario quería. La preservación de la intención es una propiedad sobre el significado de la inserción, no sobre la aritmética del espacio, y hay esquemas perfectamente densos que la incumplen cuando el vecino elegido como referencia desaparece o cuando varias inserciones concurrentes eligen el mismo hueco. Los identificadores densos son el suelo sobre el que se construye la solución, no la solución.

El ejemplo que lo deja claro es el del vecino que se borra. Elegiste una posición entre p y q porque querías estar justo detrás de lo que había en p, pero si alguien borra ese elemento de forma concurrente, tu identificador sigue siendo perfectamente válido y sigue estando entre p y q: lo que ha desaparecido es el motivo por el que lo elegiste. El sistema converge, nadie pierde datos y aun así el resultado puede no tener sentido para quien escribió. Ninguna propiedad aritmética del espacio de posiciones puede detectar eso, porque la intención vivía en el contexto y no en el número.