Enfilade (Xanadu)

Enfilades är en klass av träddatastrukturer som uppfanns av datavetaren Ted Nelson och användes i Project Xanadu "Green" design på 1970- och 1980-talen. Enfilades möjliggör snabb redigering, versionshantering, hämtning och jämförelseoperationer i en stor, korslänkad hypertextdatabas. Xanadu "Gold"-designen som började på 1990-talet använde en relaterad datastruktur som kallas Ent .

Struktur och egenskaper

Även om principerna för enfilader kan tillämpas på vilken träddatastruktur som helst, var den särskilda strukturen som användes i Xanadu-systemet ungefär som ett B-Tree . Det som utmärker enfilades är användningen av dsps och wids i indexeringsinformationen inom trädnoder.

Dsps är förskjutningar, offset eller relativa nycklar. En dsp är skillnaden i nyckel mellan en innehållande nod och den för ett underträd eller ett löv. Till exempel kan bladet för en rutnätsruta i en karta ha en viss longitud och latitud förskjutning i förhållande till det större rutnätet som representeras av underträdet som bladet är en del av. Nyckeln till ett löv av en enfilade hittas genom att kombinera alla dsps på vägen ner genom trädet till det bladet. Dsps kan också användas för annan kontextinformation som placeras uppifrån och ned på hela underträd eller innehållsområden samtidigt.

Wids är bredder, intervall eller begränsningsrutor. En wid är relativt nyckeln till ett underträd eller ett blad, men anger ett intervall av adresser som täcker alla objekt i underträdet. Wids identifierar de intressanta delarna av glest befolkade adressutrymmen. I vissa enfilader kan underträdens bredd under en given nod överlappa varandra, och i alla fall måste en sökning efter data inom ett intervall av adresser besöka alla underträd vars bredd skär sökintervallet. Wids kombineras från trädets löv, uppåt genom alla lager till roten (även om de bibehålls stegvis). Wids kan också innehålla andra sammanfattningar såsom totaler eller maxima för data.

Den relativa naturen hos wids och dsps gör att underträd kan ordnas om i en enfilad. Genom att ändra dsp högst upp i ett underträd, ändras nycklarna för all data under implicit. Redigeringsoperationer i enfilader utförs genom att "klippa ut" eller dela trädet ner i relevanta åtkomstvägar, infoga, ta bort eller omarrangera underträd och skarva ihop bitarna igen. Kostnaden för kapning och skarvning är i allmänhet stockliknande i 1-D-träd och mellan stockliknande och kvadratrotsliknande i 2-D-träd.

Underträd kan också delas mellan träd, eller länkas från flera platser i ett träd. Detta gör enfiladen till en helt beständig datastruktur med virtuell kopiering och versionshantering av innehåll. Varje användning av ett underträd ärver ett annat sammanhang från kedjan av dsps ner till den. Ändringar av en kopia skapar bara nya noder längs de klippta banorna och lämnar hela originalet på plats. Omkostnaderna för en version är mycket små, en ny versions träd är balanserat och snabbt, och dess lagringskostnad är endast relaterad till ändringar från originalet.

Endimensionella enfilader är mellanliggande mellan arrayers direkta adresserbarhet och länkade listors lätthet att infoga, radera och omarrangera. Flerdimensionella enfilader liknar lösa, omarrangerbara, versionsbara Quad-träd , Oct-träd eller K -D-träd .

Typer av enfilader i Xanadu

Model -T- enfiladen, som användes i Xanadu-designer före 1979, är en datastruktur som mycket liknar Rope . Den lagrar linjära teckensekvenser, med enkel infogning, radering, omarrangering och versionshantering, men inte med länkar eller enkel jämförelse mellan versioner. Text lagras direkt i enfiladens blad.

Senare Xanadu-designer är mer indirekta: en växande pool av delar som kan delas, kallad istream (invariant stream) är organiserad i dokument, länkar och versioner – alla med virtuella adresser – som användarna ser och arbetar med. En samling enfiladetyper hanterar dubbelriktad mappning mellan virtuella och istream-adresser. Spårning av korrespondenser och länkar mellan dokument är möjlig genom kartläggning från virtuella, till invarianta och tillbaka till virtuella adresser. Att lagra dokument med delat innehåll som minns deras identiteter och kan spåra tillbaka till alla deras utseenden kallas Transclusion .

POOM-filaden ( permutation of order-matris) är en 2D-enfilad som representerar en permutationsmatris . Detta mappar virtuell position i ett dokument till istream-positioner i det sammanslagna innehållet som dokumentet är byggt från. POOM startar en identitetsmatris, sedan varje redigering av dokumentskivorna och arrangerar om horisontella remsor av kartan. POOM kan frågas i riktningarna V->I eller I->V genom att söka i squat, breda adressintervall eller höga, smala.

Spanfilade samlar samman alla spann av istream-innehåll som används av ett dokument eller en uppsättning dokument . Att ta skärningspunkten mellan span-set från två dokument eller versioner av ett dokument påskyndar jämförelsen av dokument. Samma mekanism används för att hitta länkar från eller till ett dokument.

Granfilade organiserar lagringen av all denna information på diskar och ett nätverk av servrar .

Företagshemlighet fram till 1999

Enfilader (interna datastrukturer) och istream-adresser exponeras inte för Xanadus externa gränssnitt. Enfilades var affärshemlig information tills Xanadu-koden gjordes öppen källkod 1999, och nämndes men inte förklarades i vissa publikationer innan den tidpunkten.

Kommunikation mellan klient och server i Xanadu-systemet använder vstream-adresser i ett format som kallas tumblers .

Därför nämns inte termen Enfilade explicit i FeBe- dokumentet (Front end - Back end protocol), utan noteras istället indirekt i Xanalogical Structure och flera andra dokument. I det tidigare nämnda dokumentet noteras att xu88 baserades på "General Enfilade Theory".

Historia

1972 introducerade xu72 konceptet Enfilade. Detta kallades "Model T Enfilade", och användes i ett gränssnitt av ordbehandlingstyp. 1976 implementerade xu76 den "tightly coupled enfilade". 1980 introducerade xu80-systemet "ent", som beskrivs som en versionsfilade. 1988 använde xu88-systemet konceptet "General Enfilade Theory" av Mark S. Miller , Stuart Greene och Roger Gregory , beskrivet som "genererande datahanteringsträd med en uppåtriktad sökegenskap och samtidigt en nedåtgående omöjlig strukturell egenskap". Xu88 utökade också konceptet med Enfilade över ett distribuerat nätverk, introducerade tvådimensionella Enfilades och implementerade en algoritm för att söka igenom hela dokumentet efter överlappande Enfilade-spann. 1992 implementerade xu92 det moderna konceptet ent.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Enfilade_(Xanadu)&oldid=1076478075 "