Las enfiladas son una clase de estructuras de datos en forma de árbol inventadas por el científico informático Ted Nelson y utilizadas en los diseños "verdes" del Proyecto Xanadu de los años 1970 y 1980. Las enfiladas permiten realizar operaciones rápidas de edición, control de versiones, recuperación y comparación entre bases de datos de hipertexto de gran tamaño y con enlaces cruzados . El diseño "dorado" de Xanadu, que comenzó en los años 1990, utilizaba una estructura de datos relacionada llamada Ent .
Aunque los principios de las enfiladas se pueden aplicar a cualquier estructura de datos de árbol, la estructura particular utilizada en el sistema Xanadu era muy similar a un B-Tree . Lo que distingue a las enfiladas es el uso de dsps y wids en la información de indexación dentro de los nodos del árbol.
Los dsps son desplazamientos, compensaciones o claves relativas. Un dsp es la diferencia de clave entre un nodo contenedor y el de un subárbol u hoja. Por ejemplo, la hoja de un cuadrado de la cuadrícula de un mapa puede tener una determinada compensación de longitud y latitud en relación con la cuadrícula más grande representada por el subárbol del que forma parte la hoja. La clave de cualquier hoja de una enfilada se encuentra combinando todos los dsps en el camino que baja por el árbol hasta esa hoja. Los dsps también se pueden utilizar para otra información de contexto que se impone de arriba hacia abajo en subárboles completos o rangos de contenido a la vez.
Los wids son anchos, rangos o cuadros delimitadores. Un wid es relativo a la clave de un subárbol u hoja, pero especifica un rango de direcciones que cubre todos los elementos dentro del subárbol. Los wids identifican las partes interesantes de espacios de direcciones escasamente poblados. En algunas enfiladas, los wids de los subárboles bajo un nodo determinado pueden superponerse y, en cualquier caso, una búsqueda de datos dentro de un rango de direcciones debe visitar cualquier subárbol cuyos wids intersequen el rango de búsqueda. Los wids se combinan desde las hojas del árbol, hacia arriba a través de todas las capas hasta la raíz (aunque se mantienen de forma incremental). Los wids también pueden contener otros resúmenes como totales o máximos de datos.
La naturaleza relativa de los wids y dsps permite reorganizar los subárboles dentro de una enfilada. Al cambiar el dsp en la parte superior de un subárbol, se modifican implícitamente las claves de todos los datos que se encuentran debajo. Las operaciones de edición en las enfiladas se realizan "cortando" o dividiendo el árbol en las rutas de acceso pertinentes, insertando, eliminando o reorganizando los subárboles y uniendo las piezas nuevamente. El costo de las operaciones de corte y unión es generalmente similar al logaritmo en árboles unidimensionales y entre similar al logaritmo y similar a la raíz cuadrada en árboles bidimensionales.
Los subárboles también se pueden compartir entre árboles o vincularse desde varios lugares dentro de un árbol. Esto hace que la enfilada sea una estructura de datos completamente persistente con copia virtual y control de versiones del contenido. Cada uso de un subárbol hereda un contexto diferente de la cadena de DSP que lo incluye. Los cambios en una copia crean nuevos nodos solo a lo largo de las rutas de corte y dejan todo el original en su lugar. La sobrecarga de una versión es muy pequeña, el árbol de una nueva versión es equilibrado y rápido, y su costo de almacenamiento está relacionado solo con los cambios del original.
Las enfiladas unidimensionales son intermedias entre la direccionabilidad directa de las matrices y la facilidad de inserción, eliminación y reorganización de las listas enlazadas. Las enfiladas multidimensionales se parecen a los árboles Quad , Oct o k -d , que son flexibles, reorganizables y versionables .
La enfilada del Modelo T , utilizada en los diseños de Xanadu antes de 1979, es una estructura de datos muy parecida a la de Rope . Almacena secuencias lineales de caracteres, con fácil inserción, eliminación, reorganización y control de versiones, pero sin enlaces ni comparación sencilla entre versiones. El texto se almacena directamente en las hojas de la enfilada.
Los diseños posteriores de Xanadu son más indirectos: un conjunto creciente de piezas de contenido compartible, llamado istream (flujo invariante), se organiza en documentos, enlaces y versiones (todos con direcciones virtuales) que los usuarios ven y en los que trabajan. Una colección de tipos de enfilada gestiona el mapeo bidireccional entre direcciones virtuales y de istream. El rastreo de correspondencias y enlaces entre documentos es posible mediante el mapeo de direcciones virtuales a invariantes y de vuelta a direcciones virtuales. El almacenamiento de documentos utilizando piezas de contenido compartido que recuerdan sus identidades y pueden rastrearse hasta todas sus apariencias se denomina transclusión .
La POOMfilade (matriz de permutación de orden) es una enfilada 2D que representa una matriz de permutación . Esta asigna una posición virtual en un documento a posiciones de istream en el contenido agrupado a partir del cual se construye el documento. La POOM comienza con una matriz de identidad y luego, cada edición del documento corta y reorganiza franjas horizontales del mapa. La POOM se puede consultar en las direcciones V->I o I->V buscando en rangos de direcciones amplios y bajos o altos y estrechos.
Spanfilade recopila la unión de todos los tramos de contenido de istream utilizados por un documento o un conjunto de documentos. Tomar la intersección de conjuntos de tramos de dos documentos o versiones de un documento acelera la comparación de documentos. Este mismo mecanismo se utiliza para buscar enlaces desde o hacia un documento.
La Granfilade organiza el almacenamiento de toda esta información en discos y una red de servidores.
Las enfiladas (estructuras de datos internas) y las direcciones istream no están expuestas a las interfaces externas de Xanadu. Las enfiladas eran información comercial secreta hasta que el código de Xanadu se convirtió en código abierto en 1999, y se mencionaban, pero no se explicaban, en algunas publicaciones anteriores a ese momento. [1]
Las comunicaciones cliente-servidor en el sistema Xanadu utilizan direcciones vstream en un formato llamado tumblers .
Por lo tanto, el término Enfilade no se menciona explícitamente en el documento FeBe (protocolo Front-Back end), sino que se menciona indirectamente en Xanalogical Structure y en varios otros documentos. En el documento antes mencionado, se señala que xu88 se basó en la "teoría general de Enfilade".
En 1972, xu72 introdujo el concepto de Enfilade. Se lo denominó "Enfilade Modelo T" y se utilizó en una interfaz de procesamiento de textos. En 1976, xu76 implementó la "enfilade estrechamente acoplada". En 1980, el sistema xu80 introdujo "ent", descrito como una enfilade de control de versiones. En 1988, el sistema xu88 utilizó el concepto de "Teoría general de enfilade" de Mark S. Miller , Stuart Greene y Roger Gregory , descrito como "generar árboles de gestión de datos con una propiedad de búsqueda de propagación ascendente y simultáneamente una propiedad estructural imponible descendente". El xu88 también extendió el concepto de Enfilade a una red distribuida, introdujo Enfilades bidimensionales e implementó un algoritmo para buscar en todo el docuverso tramos de Enfilade superpuestos. En 1992, xu92 implementó el concepto moderno de ent. [2]