Skip List

Avanceret

En probabilistisk datastruktur der bruger multiple layers af linked lists til at opnå O(log n) performance.

Kompleksitet

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

Beskrivelse

Skip List er en fascinerende datastruktur der opnår samme asymptotiske performance som balanced trees (O(log n) for search, insert, delete) men med en meget simplere implementation. I stedet for komplekse rotation operations og balancing rules, bruger Skip Lists randomisering. Strukturen består af multiple levels af linked lists, hvor bottom level indeholder alle elementer sorteret, og hver højere level indeholder et subset af elementerne fra niveauet under. Når en ny node indsættes, bestemmes dens højde (hvor mange levels den skal være med i) ved at flippe en mønt - hver gang det er heads, går vi et level højere. Ved søgning starter vi fra top level og går til højre så langt som muligt uden at overskride target, derefter går vi et level ned og gentager. I gennemsnit leder dette til O(log n) performance. Skip Lists bruges i Redis sorted sets, LevelDB MemTable, og mange concurrent data structures fordi de er lettere at parallelisere end balanced trees. De er mere intuitive at forstå og implementere end Red-Black eller AVL Trees.

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 from highest level
    for (let i = this.level; i >= 0; i--) {
      // Move forward while next value is less than target
      while (current.forward[i] && current.forward[i].value < value) {
        current = current.forward[i];
      }
    }

    // Move to lowest level
    current = current.forward[0];

    // Check if we found the value
    return current && current.value === value;
  }

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

    // Find position to insert
    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];

    // If value already exists, don't insert
    if (current && current.value === value) {
      return;
    }

    // Generate random level for new node
    const newLevel = this.randomLevel();

    // If new level is higher than current max level
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) {
        update[i] = this.header;
      }
      this.level = newLevel;
    }

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

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

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

    // Find node to delete
    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];

    // If value found, remove it
    if (current && current.value === value) {
      for (let i = 0; i <= this.level; i++) {
        if (update[i].forward[i] !== current) {
          break;
        }
        update[i].forward[i] = current.forward[i];
      }

      // Update level if necessary
      while (this.level > 0 && !this.header.forward[this.level]) {
        this.level--;
      }
    }
  }

  display() {
    console.log('Skip List:');
    for (let i = this.level; i >= 0; i--) {
      let current = this.header.forward[i];
      let values = [];
      while (current) {
        values.push(current.value);
        current = current.forward[i];
      }
      console.log(`Level ${i}: ${values.join(' -> ')}`);
    }
  }
}

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

skipList.display();
console.log('Search 7:', skipList.search(7)); // true
console.log('Search 10:', skipList.search(10)); // false

skipList.delete(7);
console.log('After delete 7:', skipList.search(7)); // false

Anvendelsesområder

•Concurrent data structures (lettere at lock)
•In-memory databases og caches
•Ordered key-value stores
•Priority queues
•Alternative til balanced trees når simplicitet ønskes

Fordele

✓Meget simplere implementation end balanced trees
✓Ingen komplekse rotations eller rebalancing
✓Lock-free concurrent implementation mulig
✓God average-case performance
✓Deterministisk space complexity

Ulemper

✗Performance er probabilistisk (ikke garanteret)
✗Bruger mere memory end simple linked lists
✗Worst case er O(n) ved meget uheldig randomness
✗Cache-unfriendly pga. pointer chasing
✗Mindre kendt end balanced trees

Eksempler fra den virkelige verden

•Redis Sorted Sets implementation
•LevelDB/RocksDB MemTable
•Lucene (Apache) inverted indexes
•HBase MemStore
•Concurrent skip lists i Java ConcurrentSkipListMap

Relaterede strukturer

Linked ListBinary Search TreeB-TreeHash Table