Veri yapısı, bir programın bilgiyi yalnız nerede tuttuğunu değil, hangi ilişkiler içinde gördüğünü ve bu bilgi üzerinde hangi işlemleri verimli biçimde yapabildiğini belirler. Aynı kayıtlar ardışık bir dizi, bağlantılı bir liste, dallanan bir ağaç, anahtarlarla erişilen bir karma tablosu veya düğümler arasındaki ilişkileri gösteren bir çizge içinde düzenlenebilir. Bu gösterimlerin her biri farklı soruları kolaylaştırır ve başka işlemleri pahalılaştırır. Bu nedenle seçim, programlama dilindeki hazır bir sınıfı çağırmaktan önce problemin erişim örüntüsünü anlamayı gerektirir. Verinin ne sıklıkla arandığı, hangi sırayla güncellendiği, belleğe sığıp sığmadığı, eş zamanlı kullanıcılarca değiştirilip değiştirilmediği ve kalıcı depolamaya aktarılıp aktarılmayacağı birlikte değerlendirilir. İyi tasarlanmış bir yapı, algoritmanın varsayımlarını açıklar; kötü seçim ise doğru yöntemi gereksiz bellek tüketen veya ölçek büyüdüğünde kullanılamaz hâle gelen bir uygulamaya dönüştürebilir.
Veri yapısının problemden işleme uzanan düzeni
- Veri Öğeler, türler ve geçerli değerler
- İlişki Sıra, üyelik, öncelik ve bağlantı
- İşlem Arama, ekleme, silme ve dolaşma
- Maliyet Zaman, bellek ve depolama erişimi
- Doğrulama Değişmezler ve sınır durumları
Soyut veri türü ile somut gösterim
Soyut veri türü, bir veri topluluğunun dışarıdan görülen davranışını tanımlar. Yığın için son eklenen öğeyi çıkarma, kuyruk için ilk gireni önce alma, küme için üyelik ve yinelenmeme gibi kurallar bu düzeydedir. Öğelerin bellekte ardışık tutulması, düğümlerin göstergelerle bağlanması veya bir karma işleviyle yuvalara dağıtılması ise somut gerçekleştirim kararıdır. Aynı soyut davranış birden çok gösterimle sağlanabilir. Bu ayrım, kullanıcı kodunun iç düzen değişse de geçerli kalmasını ve performans kararının arayüzden bağımsız sınanmasını sağlar.
Somut gösterim yalnız hız ayrıntısı değildir; hangi hataların mümkün olduğunu da değiştirir. Bağlantılı listede kopuk düğüm veya çevrim oluşabilirken, sabit boyutlu dizide kapasite aşımıyla karşılaşılır. Dengeli ağaç sıralı erişimi korumak için her güncellemeden sonra yüksekliğini sınırlayan kurallara ihtiyaç duyar. Bu kurallar veri yapısının değişmezleridir. Ekleme ve silme işlemleri yalnız yeni sonucu üretmekle kalmaz, bütün değişmezleri korumalıdır. Tasarım belgesinde soyut sözleşme ile bellekteki düzen ayrı yazıldığında doğruluk incelemesi ve gerçekleştirim değişikliği daha yönetilebilir olur.
Doğrusal, ağaçsal ve ağ biçimli yapılar
Dizi ve liste gibi doğrusal yapılar öğeleri izlenebilir bir sıra içinde tutar. Dizi konumu bilinen öğeye hızlı erişim verir; ortasına ekleme ise sonraki öğelerin taşınmasını gerektirebilir. Bağlantılı liste yer değiştirmeden ekleme yapabilir, fakat belirli sıradaki öğeye ulaşmak için önceki düğümleri izler. Yığın ve kuyruk, bu düzenler üzerinde erişim sırasını kısıtlayan yapılardır. Öncelik kuyruğu giriş zamanını değil öncelik değerini izler. Seçim, “hangisi daha hızlı” sorusundan çok, baskın işlemin ve beklenen veri büyüklüğünün ne olduğuna bağlıdır.
Ağaçlar üst-alt ilişkisini, çizgeler ise çok yönlü bağlantıları gösterir. Arama ağacı anahtar sırasını kullanarak olası konumları daraltabilir; yığın ağacı en yüksek veya en düşük öncelikli öğeyi kökte tutar. Ön ek ağacı karakter dizilerinin ortak başlangıçlarını paylaşarak sözlük ve tamamlama uygulamalarında yarar sağlar. Çizgede düğümler kişi, şehir, belge ya da durum; kenarlar ise bunlar arasındaki ilişki olabilir. Yön, ağırlık ve çoklu bağlantı gibi özellikler problemin anlamından gelir. Gerçek dünyadaki her ilişkiyi tek yapıya doldurmak açıklığı azaltabileceği için modelin sınırı önceden belirlenir.
Arama, karma ve indeksleme
Bir öğeyi bulma maliyeti düzenin taşıdığı bilgiden yararlanır. Sırasız dizide hedef, en kötü durumda bütün öğeler görülerek bulunur. Sıralı dizide ikili arama aralığı her adımda daraltabilir, ancak sıralılığı korumak güncellemeyi pahalılaştırır. Karma tablosu anahtarı bir yuvaya eşleyerek ortalama durumda hızlı erişim sunar; farklı anahtarların aynı yuvaya düşmesi için açık bir çakışma yöntemi gerekir. Karma işlevinin dağılımı, doluluk oranı ve yeniden boyutlandırma eşiği gerçek performansı belirler. Yalnız kuramsal ortalamaya bakmak kötü anahtar dağılımını görünmez kılabilir.
Veri tabanı indeksi de belirli sütun veya bileşik anahtar üzerinde ek bir erişim yapısı kurar. İndeks okumayı hızlandırırken depolama alanı kullanır ve her yazmada güncellenir. Bu nedenle bütün alanları indekslemek genel bir çözüm değildir. Aralık sorguları, tam eşleşme, metin araması ve uzamsal yakınlık farklı yapılar ister. Bellek içi yapı ile disk üzerindeki yapı da aynı ölçütle değerlendirilmez: Depolama sayfasına yapılan erişim işlemci karşılaştırmasından çok daha pahalı olabilir. B-ağaçları gibi yapılar geniş dallanmayla disk erişimini azaltmayı amaçlar.
Karmaşıklık, bellek ve yerellik
İşlemler tek bir “hız” değeriyle tanımlanmaz. Arama, ekleme, silme, en küçük öğeyi bulma ve bütün yapıyı dolaşma için ayrı karmaşıklıklar vardır. En kötü durum, ortalama durum ve amortismanlı maliyet farklı sorulara yanıt verir. Dinamik dizinin seyrek gerçekleşen yeniden boyutlandırması tek işlemde pahalı olsa da uzun bir ekleme dizisine yayıldığında öğe başına sınırlı maliyet doğurabilir. Büyük O gösterimi büyüme eğilimini açıklar; sabit maliyetleri, veri dağılımını ve donanım davranışını tek başına öngörmez. Kuramsal karşılaştırma ölçümle tamamlanır.
Modern işlemciler yakın bellek konumlarına art arda erişimi önbellek sayesinde verimli işler. Bu yüzden ardışık dizide dolaşmak, aynı asimptotik sınıftaki dağınık düğüm ziyaretlerinden daha hızlı olabilir. Gösterge ve nesne üst bilgisi de büyük koleksiyonlarda belirgin alan tüketir. Sıkıştırılmış yapılar belleği azaltırken güncellemeyi zorlaştırabilir. Çok iş parçacıklı kullanımda kilitlerin kapsamı, atomik işlemler ve yanlış paylaşım maliyete eklenir. Yapı seçimi gerçek veri boyutu ve erişim iziyle karşılaştırmalı ölçüldüğünde donanıma özgü etkiler görünür hâle gelir.
Kalıcılık, eş zamanlılık ve hata dayanımı
Bellekte doğru çalışan yapı, süreç kapandığında bilgiyi korumaz. Kalıcı yapılarda kayıt biçimi, yazma sırası ve yarım kalan işlemin nasıl toparlanacağı tasarımın parçasıdır. Günlükleme önce niyeti kaydedip sonra ana yapıyı değiştirebilir; kopyala-yaz yaklaşımı eski sürümü koruyarak yeni sayfalar oluşturabilir. Çökme anında hangi durumun geçerli sayılacağı açık değilse veri yapısı fiziksel olarak okunabilir olsa bile mantıksal bütünlüğünü kaybedebilir. Sağlama toplamı bozuk sayfayı saptar, fakat doğru kurtarma kuralının yerini tutmaz.
Eş zamanlı erişimde iki işlem ayrı ayrı doğru adımlar yürütüp birlikte değişmezi bozabilir. Basit çözüm bütün yapıyı tek kilitle korumaktır; bu kez bekleme artar ve paralellik azalır. İnce taneli kilit, sürüm numarası veya kilitsiz algoritma daha çok eş zamanlılık sağlayabilir, ancak kanıtı ve sınaması güçleşir. Okuyucu-yazıcı dengesi, açlık ve kilitlenme olasılığı incelenir. Dağıtık kopyalarda sorun yalnız bellek yarışı değildir; gecikmiş iletiler ve ağ bölünmesi hangi sürümün geçerli olduğunu belirsizleştirebilir. Bu durumda tutarlılık modeli veri yapısının dış sözleşmesine dönüşür.
Seçim, sınama ve GTS bağlantısı
Uygun yapı, beklenen işlemlerin oranı ve hizmet düzeyi hedefi yazılarak seçilir. Küçük veri üzerinde yalın bir liste, karmaşık bir indeks düzeninden daha güvenilir olabilir. Ölçek büyüdüğünde arama gecikmesi, bellek sınırı veya yazma maliyeti yeniden değerlendirilir. Sınama boş yapı, tek öğe, yinelenen anahtar, en büyük kapasite ve ardışık silme gibi sınır durumlarını içerir. Özellik tabanlı testler, işlem dizilerinden sonra boyutun ve sıralamanın korunmasını denetleyebilir. Ölçüm, yapıların aynı işi yaptığı doğrulandıktan sonra ve aynı veri dağılımında yürütülür.
T-BDLD'de “veri yapısı”, “veri yapıları”, “karma tablosu”, “bağlantılı liste” ve “arama ağacı” sorguları teknik terimin akademik, öğretici ve genel metinlerdeki dağılımını canlı gösterir. Kod parçaları, içindekiler listeleri ve kaynakça dizileri bağlam sayısını yapay biçimde yükseltebileceğinden cümle bütünlüğü ayrıca denetlenir. “Yapı” sözcüğünün genel anlamları teknik kullanımla karıştırılmaz. Ansiklopedi açıklaması kaynaklarla kurulan kavramsal çerçeveyi korurken derlem kartı yeni veri geldikçe sıklık, kaynak dağılımı ve son görülme zamanını günceller.
Doğrulanmış kaynakça
- Association for Computing Machinery, IEEE Computer Society ve Association for the Advancement of Artificial Intelligence (2024). Computer Science Curricula 2023: The Final Report. Kaynağı aç
- Black, Paul E. (2020). DADS: The On-Line Dictionary of Algorithms and Data Structures. NISTIR 8318. National Institute of Standards and Technology. DOI: 10.6028/NIST.IR.8318. Kaynağı aç
- Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest ve Clifford Stein (2022). Introduction to Algorithms. 4. baskı. The MIT Press. Kaynağı aç