Skip List

Avanceret

En probabilistisk datastruktur der bruger flere lag af lænkede lister til at opnå O(log n) ydeevne.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(log n) gennemsnit`
Search	`O(log n) gennemsnit`
Insertion	`O(log n) gennemsnit`
Deletion	`O(log n) gennemsnit`

Beskrivelse

Skip List er en fascinerende datastruktur der opnår samme asymptotiske ydeevne som balancerede træer (O(log n) for søgning, indsættelse, sletning) men med en meget simplere implementering. I stedet for komplekse rotationsoperationer og balanceringsregler bruger Skip Lists randomisering. Strukturen består af flere niveauer af lænkede lister, hvor bundniveauet indeholder alle elementer sorteret, og hvert højere niveau indeholder et undersæt af elementerne fra niveauet under. Når en ny node indsættes, bestemmes dens højde (hvor mange niveauer den skal være med i) ved at slå plat og krone - hver gang det er krone, går vi et niveau højere. Ved søgning starter vi fra topniveauet og går til højre så langt som muligt uden at overskride målet, derefter går vi et niveau ned og gentager. I gennemsnit leder dette til O(log n) ydeevne. Skip Lists bruges i Redis sorterede sæt, LevelDB MemTable, og mange samtidige datastrukturer fordi de er lettere at parallelisere end balancerede træer. De er mere intuitive at forstå og implementere end rød-sort- eller AVL-træer.

Kode Eksempel

// JavaScript Skip List Implementation
class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  constructor(maxLevel = 16, probability = 0.5) {
    this.maxLevel = maxLevel;
    this.probability = probability;
    this.level = 0;
    this.header = new SkipListNode(-Infinity, maxLevel);
  }

  randomLevel() {
    let level = 0;
    while (Math.random() < this.probability && level < this.maxLevel) {
      level++;
    }
    return level;
  }

  search(value) {
    let current = this.header;

    // Start fra højeste niveau
    for (let i = this.level; i >= 0; i--) {
      // Bevæg fremad mens næste værdi er mindre end mål
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
    }

    // Gå til laveste niveau
    current = current.forward[0];

    // Tjek om vi fandt værdien
    return current && current.value === value;
  }

  insert(value) {
    const update = new Array(this.maxLevel + 1).fill(null);
    let current = this.header;

    // Find position at indsætte
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }

    current = current.forward[0];

    // Hvis værdi allerede findes, indsæt ikke
    if (current && current.value === value) {
      return;
    }

    // Generer tilfældigt niveau for ny node
    const newLevel = this.randomLevel();

    // Hvis nyt niveau er højere end nuværende max niveau
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) {
        update[i] = this.header;
      }
      this.level = newLevel;
    }

    // Opret ny node
    const newNode = new SkipListNode(value, newLevel);

    // Opdater forward pointers
    for (let i = 0; i <= newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }
}

// Brug
const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
skipList.insert(9);

console.log('Søg 7:', skipList.search(7)); // true
console.log('Søg 10:', skipList.search(10)); // false

Anvendelsesområder

•Samtidige datastrukturer (lettere at låse)
•Hukommelsesdatabaser og caches
•Ordnede nøgle-værdi-lagre
•Prioritetskøer
•Alternativ til balancerede træer når simplicitet ønskes

Fordele

✓Meget simplere implementering end balancerede træer
✓Ingen komplekse rotationer eller rebalancering
✓Låsefri samtidige implementeringer mulige
✓God gennemsnitlig ydeevne
✓Deterministisk pladskompleksitet

Ulemper

✗Ydeevne er probabilistisk (ikke garanteret)
✗Bruger mere hukommelse end simple lænkede lister
✗Værste tilfælde er O(n) ved meget uheldig tilfældighed
✗Cache-uvenlig pga. pointer-følgning
✗Mindre kendt end balancerede træer

Eksempler fra den virkelige verden

•Redis sorterede sæt-implementering
•LevelDB/RocksDB MemTable
•Lucene (Apache) inverterede indekser
•HBase MemStore
•Samtidige skip lists i Java ConcurrentSkipListMap

Relaterede strukturer

Linked ListBinary Search TreeB-TreeHash Table