Bu veri yapısı sanırım en çok concurrent yani çoklu thread kullanan ortamlarda daha verimli. Binary Search Tree gibi veri yapılarında rebalance işlemi için tüm ağacı kilitlemek gerekiyor. Açıklaması şöyle
The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.
Bu yüzden Java'da
gibi concurrent veri yapıları da var
Nasıl Çalışır
Bir anlamda Linked List'e benzer. Farklı olarak her düğüm ilave olarak N sonraki düğümlere de pointer tutar. N sayısı 2, 4 gibi bir şey olabilir.
Örnek
Şeklen şöyle. Burada her düğüm 2 sonraki düğüme de pointer tutuyor. Dolayısıyla 80 değerini aramak için 7 defa işlem yerine, 4 işlem yeterli.
Hiç yorum yok:
Yorum Gönder