Neden gerekli?
Veriler disk tabanlı depolama aygıtlarında depolandığında, veri blokları olarak depolanır. Bu bloklara, atom disk erişim işlemi yaparak bütünüyle erişilir. Disk blokları, bağlantılı listelerle aynı şekilde yapılandırılmıştır; her ikisi de veri için bir bölüm, bir sonraki düğümün (veya bloğun) konumuna bir işaretçi içerir ve her ikisinin de bitişik olarak depolanması gerekmez.
Kayıtların bir numara sadece bir alanda sıralanabilir gerçeği nedeniyle, sıralanmamıştır bir alanda arama gerektiren bir Doğrusal Arama gerektirdiğini ifade edebiliriz
N/2 blok erişimler (ortalama olarak), nerede
N blok sayısı olduğunu masa yayılır. Bu alan kilit olmayan bir alan ise (yani benzersiz girişler içermiyorsa),
N blok erişimlerinde tüm tablo alanının aranması gerekir .
Sıralanmış bir alana sahipken,
log2 N blok erişimi olan bir İkili Arama kullanılabilir . Ayrıca, veriler kilit olmayan bir alana göre sıralandığından, tablonun geri kalanının, daha yüksek bir değer bulunduğunda, yinelenen değerler için aranmasına gerek yoktur. Bu nedenle performans artışı önemli.
İndeksleme nedir?
İndeksleme, birden çok alanda bir dizi kaydı sıralamanın bir yoludur. Tablodaki bir alanda bir dizin oluşturmak, alan değerini tutan başka bir veri yapısı ve ilgili kayıtlara bir işaretçi oluşturur. Bu indeks yapısı daha sonra İkili Aramaların üzerinde yapılmasına izin verecek şekilde sıralanır.
İndekslemenin dezavantajı, endekslerin MyISAM motorunu kullanarak bir tabloda birlikte depolandığından, bu indekslerin disk üzerinde ek alan gerektirmesidir; bu dosya, aynı tabloda bulunan birçok alanın endekslenmesi durumunda, temel dosya sisteminin boyut sınırlarına hızla ulaşabilir. .
O nasıl çalışır?
İlk olarak, bir örnek veritabanı tablosu şeması özetleyelim;
Alan adı Veri türü Diskteki boyut
id (Birincil anahtar) İmzasız INT 4 bayt
firstName Char (50) 50 bayt
lastName Char (50) 50 bayt
emailAdresi Char (100) 100 bayt
Not : char, disk değerinde doğru bir boyut elde etmek için varchar yerine kullanıldı. Bu örnek veritabanı beş milyon satır içeriyor ve indekslenmemiş. Birkaç sorgunun performansı şimdi analiz edilecektir. Bunlar, id (sıralı bir anahtar alan) ve firstName (anahtar olmayan bir sıralanmamış alan) kullanan bir sorgu .
Örnek 1 - sıralanmamış alanlara göre sıralanmış
r = 5,000,000 Kayıt büyüklüğünde
R = 204 bayt veren sabit büyüklükteki kayıt veri tabanımız göz önüne alındığında , varsayılan blok büyüklüğü
B = 1,024 bayt kullanan MyISAM motoru kullanılarak bir tabloda saklanır . Tablonun engelleme faktörü,
bfr = (B/R) = 1024/204 = 5 disk bloğu başına kayıt olacaktır . Masayı tutmak için gereken toplam blok sayısı
N = (r/bfr) = 5000000/5 = 1,000,000 bloktur.
İd alanındaki doğrusal bir arama, id alanının
N/2 = 500,000 anahtar bir alan olduğu göz önüne alındığında, bir değer bulmak için ortalama bir blok erişim gerektirir . Ancak id alanı da sıralandığından, ortalama
log2 1000000 = 19.93 = 20 blok erişim gerektiren bir ikili arama yapılabilir . Anında görebiliyoruz ki bu şiddetli bir gelişme.
Şimdi, firstName alanı ne sıralanır ne de bir anahtar alandır, bu nedenle ikili arama imkansız değildir, ne de değerler benzersiz değildir ve bu nedenle tablo tam bir
N = 1,000,000 blok erişimi için sonuna kadar arama yapmayı gerektirir . İndekslemenin düzeltmeyi amaçladığı durum budur.
Bir dizin kaydının yalnızca dizine alınmış alanı ve orijinal kaydın bir göstergesini içerdiği göz önüne alındığında, işaret ettiği çoklu alan kaydından daha küçük olmasının nedeni budur. Bu yüzden endeksin kendisi orijinal tablodan daha az disk bloğu gerektirir, bu nedenle yinelemek için daha az blok erişimi gerektirir. FirstName alanındaki bir dizinin şeması aşağıda özetlenmiştir;
Alan adı Veri türü Diskteki boyut
firstName Char (50) 50 bayt
(kayıt işaretçisi) Özel 4 bayt
Not : MySQL'deki işaretçiler, tablonun boyutuna bağlı olarak uzunlukları 2, 3, 4 veya 5 bayttır.
Örnek 2 - indeksleme
r = 5,000,000 İndeks kayıt
R = 54 bayt uzunluğuna sahip ve varsayılan blok büyüklüğündeki
B = 1,024 baytları kullanan kayıt veri tabanımıza göre Endeksin blokaj faktörü,
bfr = (B/R) = 1024/54 = 18 disk bloğu başına kayıt olacaktır . Dizini tutmak için gereken toplam blok sayısı
N = (r/bfr) = 5000000/18 = 277,778 bloktur.
Şimdi firstName alanını kullanan bir arama, performansı artırmak için dizini kullanabilir. Bu, indeks üzerinde ortalama
log2 277778 = 18.08 = 19 blok erişimli bir ikili arama yapılmasına izin verir . Okumak için daha fazla blok erişimi gerektiren asıl kaydın adresini bulmak, toplam erişimi engellemek için, dizin oluşturulmuş olmayan tabloda
19 + 1 = 20 bir ilk ad eşleşmesi bulmak için gereken 1.000.000 blok erişiminden çok uzakta .
Ne zaman kullanılmalı?
Dizin oluşturmanın ek disk alanı gerektirdiği (yukarıdaki örnekten 277.778 blok fazla,% ~ 28 artış) ve çok fazla endeksin dosya sistemi boyut sınırlarından kaynaklanan sorunlara neden olabileceği göz önüne alındığında, doğru seçimi seçmek için dikkatli düşünmek gerekir. endekslenecek alanlar.
Endeksler yalnızca kayıtlar içinde eşleşen bir alan aramasını hızlandırmak için kullanıldığından, yalnızca çıktı için kullanılan endeksleme alanlarının basitçe bir ekleme veya silme işlemi yaparken disk alanı ve işleme zamanının boşa harcanması, ve böylece kaçınılmalıdır. Ayrıca, ikili bir aramanın niteliği göz önüne alındığında, verinin önemliliği veya benzersizliği önemlidir. Kardinalliği 2 olan bir alanda indeksleme işlemi verileri ikiye bölerken 1000 kardinalitesi yaklaşık 1.000 kayıt verir. Böyle düşük bir kardinalite ile, etkinlik doğrusal bir sıralamaya indirgenir ve sorgu optimize edici, eğer kardinalite kayıt numarasının% 30'undan azsa endeksi kullanmaktan kaçınır ve endeksi etkin bir şekilde boşa harcar.