DBMS'de Hashing: Statik ve Dinamik Hashing Teknikleri

By: Fiona Brown Fiona Brown
Hours GรผncellenmiลŸ

โšก 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.

  • โšก Ana dรผลŸรผnce: Karma fonksiyonu, bir anahtarฤฑ bir kova adresine dรถnรผลŸtรผrรผr; bรถylece bir kayฤฑt, dizin taramasฤฑ yerine tek bir adฤฑmda bulunur.
  • ๐Ÿชฃ Veri Kovasฤฑ: Aynฤฑ karma deฤŸerine sahip kayฤฑtlarฤฑn yerleลŸtirildiฤŸi bellek konumu veya depolama birimi.
  • ๐Ÿ“Œ Statik Karma Fonksiyonu: Kova sayฤฑsฤฑ sabittir, bu nedenle belirli bir anahtar her zaman aynฤฑ adrese eลŸlenir.
  • ๐Ÿ“ˆ Dinamik Karma Fonksiyonu: Veri hacmi deฤŸiลŸtikรงe, talep รผzerine kovalar eklenir ve kaldฤฑrฤฑlฤฑr.
  • ๐Ÿ’ฅ ร‡arpฤฑลŸma: ฤฐki anahtar haritasฤฑping Aynฤฑ kovaya, sorgulama, yeniden karma oluลŸturma veya zincirleme yoluyla รงรถzรผmlenir.
  • ๐Ÿ” En: Arama anahtarฤฑnda tam eลŸleลŸme aramalarฤฑ, burada karma algoritmasฤฑ sฤฑralฤฑ indekslemeye gรถre daha iyi performans gรถsterir.
  • ๐Ÿ“Š DeฤŸiลŸ tokuลŸ: Aralฤฑk sorgularฤฑ iรงin sฤฑralฤฑ indeksleme, sabit deฤŸer ekleme ve nokta arama iลŸlemleri iรงin ise karma fonksiyonlar daha avantajlฤฑdฤฑr.
Devamฤฑnฤฑ Oku

Veritabanฤฑ Yรถnetim Sistemlerinde Statik ve Dinamik Karma Fonksiyonlarฤฑ

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:

  1. Statik Karma
  2. 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.

ฤฐLGฤฐLฤฐ MAKALELER

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:

  1. Aรงฤฑk karma
  2. 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.

Aรงฤฑk karma algoritmasฤฑnฤฑn doฤŸrusal sorgulama ile nasฤฑl รงalฤฑลŸtฤฑฤŸฤฑ
Aรงฤฑk Karma Nasฤฑl ร‡alฤฑลŸฤฑr?

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:

  1. 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.
  2. 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.

SSS

Statik karma algoritmasฤฑ sabit sayฤฑda kova tutar, bu nedenle veri miktarฤฑ arttฤฑkรงa taลŸma riski vardฤฑr. Dinamik karma algoritmasฤฑ ise isteฤŸe baฤŸlฤฑ olarak kova ekler ve kaldฤฑrฤฑr, bu nedenle tam bir yeniden yapฤฑlandฤฑrmaya gerek kalmadan deฤŸiลŸen veri boyutuna uyum saฤŸlar.

Aralฤฑk sorgularฤฑ iรงin. Karma algoritmasฤฑ anahtarlarฤฑ gruplara daฤŸฤฑtฤฑr, bu nedenle "arasฤฑnda" veya "bรผyรผktรผr" sorgularฤฑ bunlarฤฑ sฤฑrayla gezemez. Sฤฑralฤฑ indeks anahtarlarฤฑ sฤฑralฤฑ tutar ve bu nedenle daha uygundur.

Bir kova, tutabileceฤŸinden daha fazla kayฤฑt karma iลŸlemine tabi tutulduฤŸunda taลŸar. Statik karma iลŸleminde, veriler bรผyรผdรผkรงe bu durum sฤฑkรงa yaลŸanฤฑr ve aรงฤฑk adresleme, zincirleme veya taลŸma kovalarฤฑ ile ele alฤฑnฤฑr.

Yapay zekรข sistemleri, hฤฑzlฤฑ รถzellik aramasฤฑ ve yรผksek kardinaliteli kategorileri sabit bir vektรถre eลŸleyen karma algoritmasฤฑ (hashing trick) iรงin karma algoritmasฤฑnฤฑ kullanฤฑr. Benzerlik karma algoritmasฤฑ ayrฤฑca birbirine รงok benzeyen kayฤฑtlarฤฑ verimli bir ลŸekilde gruplandฤฑrฤฑr.

Yeniden karma iลŸlemi, ikinci bir fonksiyon kullanarak aynฤฑ tabloda baลŸka bir boลŸ yer bulur. Zincirleme iลŸlemi, รงakฤฑลŸan kayฤฑtlarฤฑ kovaya baฤŸlฤฑ baฤŸlantฤฑlฤฑ bir listede tutar, bรถylece tablo hiรงbir zaman bir yeri iki kez doldurmaz.

Bu yazฤฑyฤฑ ลŸu ลŸekilde รถzetleyin: