DBMS'de Hashing: Statik ve Dinamik Hashing Teknikleri
Editoryal Takım
⚡ Akıllı Özet
Veritabanı yönetim sistemlerinde (DBMS) karma (hashing), bir kaydın disk konumunu dizin taraması yapmadan doğrudan anahtarından hesaplayan bir tekniktir. Karma fonksiyonu, arama anahtarlarını veri kovalarına eşler ve statik veya dinamik karma, bu kovaların nasıl büyüyeceğini yönetir.
DBMS'de Hashing nedir?
Veritabanı yönetim sistemlerinde (DBMS), karma (hashing), indeks yapısı kullanmadan disk üzerindeki istenen verinin konumunu doğrudan arama tekniğidir. Karma yöntemi, veritabanındaki öğeleri indekslemek ve almak için kullanılır, çünkü belirli bir öğeyi orijinal değerinden ziyade daha kısa karma anahtar kullanarak aramak daha hızlıdır. Veriler, adresleri bir karma fonksiyonu uygulanarak oluşturulan veri blokları şeklinde saklanır; bu kayıtların saklandığı bellek konumu, dizin olarak bilinir. veri bloğu veya veri kümesi.
Karma fonksiyonlara neden ihtiyacımız var?
Veritabanı yönetim sistemlerinde (DBMS) karma (hashing) yöntemini uygulamanız gereken durumlar şunlardır:
- Büyük bir veritabanı yapısında, tüm indeks değerlerini tüm seviyeler boyunca aramak ve ardından istenen veriye ulaşmak için hedef veri bloğuna erişmek zordur.
- Veritabanındaki öğeleri indekslemek ve almak için karma (hashing) yöntemi kullanılır, çünkü belirli bir öğeyi aramak için orijinal değerden daha kısa olan karma anahtar kullanmak daha hızlıdır.
- Karma algoritması, indeks yapısı kullanmadan disk üzerindeki bir veri kaydının doğrudan konumunu hesaplamak için ideal bir yöntemdir.
- Aynı zamanda sözlüklerin uygulanmasında da yararlı bir tekniktir.
Hashing'de Önemli Terminolojiler
İşte karma algoritmalarında kullanılan önemli terimler:
- Veri kovası: Veri kovaları, kayıtların depolandığı bellek konumlarıdır. Aynı zamanda depolama birimi olarak da bilinir.
- anahtar: a DBMS anahtarı Bir ilişkideki (tablodaki) bir satırı (kayıtı) tanımlamanıza yardımcı olan bir özellik veya özellikler kümesidir.
- Karma işlevi: bir haritaping Arama anahtarlarının tümünü, gerçek kayıtların bulunduğu adrese eşleyen fonksiyon.
- Doğrusal Sondalama: Sorgulamalar arasında sabit bir aralık bulunur. Bu yöntemde, eski kaydın üzerine yazmak yerine, yeni kaydı girmek için bir sonraki kullanılabilir veri bloğu kullanılır.
- İkinci Dereceden Sondalama: Orijinal hesaplamayla elde edilen başlangıç değerine ikinci dereceden bir polinomun ardışık çıktısını ekleyerek yeni kova adresini belirlemeye yardımcı olur.
- Karma indeks: Veri bloğunun adresi. Bir karma fonksiyonu basit bir matematiksel fonksiyon veya karmaşık bir fonksiyon olabilir.
- Double Karma: Karma tablolarında çakışmaları gidermek için ikinci bir karma fonksiyonu uygulayarak kullanılan bir yöntem.
- Kova Taşması: Kova taşması durumuna çarpışma denir. Bu, herhangi bir statik karma fonksiyonu için ölümcül bir aşamadır.
Hashing Tekniklerinin Türleri
Veritabanı yönetim sistemlerinde (DBMS) temel olarak iki tür karma algoritması tekniği vardır:
- Statik Karma
- Dinamik Karma
İki yöntem arasındaki temel fark, kova sayısının sabit olup olmamasıdır; bu durum sonraki iki bölümde açıklanmaktadır.
Statik Karma
Statik karma işleminde, elde edilen veri kovası adresi her zaman aynı kalır.
Dolayısıyla, örneğin, bir adres oluşturursanız, Öğrenci_ID = 10 karma fonksiyonunu kullanarak mod(3), sonuçta ortaya çıkan paket adresi her zaman olacaktır 1Dolayısıyla kova adresinde herhangi bir değişiklik görmeyeceksiniz.
Bu nedenle, statik karma yönteminde bellekteki veri kovalarının sayısı her zaman sabit kalır.
Statik Karma İşlevleri
- Kayıt ekleme: Tabloya yeni bir kayıt eklenmesi gerektiğinde, bu kayıt için karma anahtarını kullanarak bir adres oluşturulur. Adres oluşturulduktan sonra, kayıt o konumda saklanır.
- Aranıyor: Kaydı almak gerektiğinde, verinin saklandığı kovanın adresini almak için aynı karma işlevi kullanılır.
- Bir kaydı silme: Karma fonksiyonunu kullanarak, önce silmek istediğiniz kaydı alırsınız, ardından o adresi bellekten kaldırırsınız.
Statik karma algoritması ayrıca şu alt kategorilere ayrılır:
- Açık karma
- Kapalı karma algoritması
Hashing'i aç
Açık karma yönteminde, eski kaydın üzerine yazmak yerine, yeni kaydı girmek için bir sonraki kullanılabilir veri bloğu kullanılır. Bu yöntem aynı zamanda doğrusal sorgulama olarak da bilinir.
Örneğin, A2 eklemek istediğiniz yeni bir kayıttır. Karma fonksiyonu 222 adresini oluşturur, ancak bu adres zaten başka bir değer tarafından kullanılmaktadır. Bu nedenle sistem bir sonraki veri kovasını, 501'i arar ve A2'yi ona atar.
Kapalı Karma
Kapalı karma yönteminde, kovalar dolduğunda aynı karma için yeni bir kova tahsis edilir ve sonuç bir öncekine bağlanır.
Dinamik Karma
Dinamik karma algoritması, veri gruplarının dinamik olarak ve isteğe bağlı olarak eklenip çıkarıldığı bir mekanizma sunar. Bu karma yönteminde, karma fonksiyonu çok sayıda değer oluşturmanıza yardımcı olur ve yapı verilerle birlikte büyür veya küçülür. Bu da, statik karma algoritmasının ya yer israfına yol açacağı ya da taşmaya neden olacağı, boyutu önceden tahmin edilemeyen tablolar için ideal bir çözüm olmasını sağlar.
Sıralı İndeksleme ve Karma Fonksiyonu Arasındaki Fark
Aşağıda indeksleme ve karma algoritmaları arasındaki temel farklar yer almaktadır:
| Parametreler | Sıralı İndeksleme | Çırpı |
|---|---|---|
| Adresin saklanması | Bellekteki adresler, birincil anahtar adı verilen bir anahtar değerine göre sıralanır. | Adresler her zaman anahtar değer üzerinde bir karma işlevi kullanılarak oluşturulur. |
| Performans | Veri sayısı arttıkça bu değer azalabilir, çünkü veriler sıralı olarak saklanır ve her ekleme, silme veya güncelleme işlemi verilerin sırasını değiştirir. | Verilerin sürekli eklenmesi ve silinmesi durumunda performans en üst düzeye çıkar. Çok büyük veritabanları için hash dosyasının bakımı daha maliyetli hale gelir. |
| İçin kullanmak | Belirli bir aralık için veri alınması gereken aralık alma işlemleri için tercih edilir. | Arama anahtarına göre belirli bir kaydı almak için idealdir ve yalnızca karma işlevi arama anahtarında olduğunda iyi performans gösterir. |
| Bellek yönetimi | Silme ve güncelleme işlemlerinden kaynaklanan ve yeniden kullanım için serbest bırakılamayan birçok kullanılmayan veri bloğu vardır, bu nedenle düzenli bakım gereklidir. | Statik ve dinamik karma algoritmalarında, bellek her zaman yönetilir ve kova taşması statik karma algoritmasını genişletmek için ele alınır. |
Özetle, sıralı olanı seçin. indeksleme Aralık sorguları için ve anahtar üzerinde tam eşleşme aramaları için karma fonksiyonlar kullanılır.
Çarpışma Nedir?
Karma çakışması, veri kümesindeki iki veya daha fazla öğenin sonuçtaki karma değerlerinin yanlışlıkla aynı yere eşlenmesi durumudur. karma tablo.
Karma Çarpışmasıyla Nasıl Başa Çıkılır?
Karma çakışmasını önlemek için kullanabileceğiniz iki teknik vardır:
- Tekrar ele almak: Bu yöntem, boş bir kayıt yuvası bulunana kadar sürekli olarak uygulanan ikincil bir karma işlevini çağırır.
- Zincirleme: Zincirleme yöntemi, anahtarları aynı karma değere sahip öğelerden oluşan bağlantılı bir liste oluşturur. Bu yöntem, tablonun her konumunda fazladan bir bağlantı alanı gerektirir.
