Apakah kolom yang bukan indeks, diurutkan pada disk bersama dengan indeks?

8

Apakah kolom yang bukan indeks, diurutkan pada disk bersama dengan indeks, di MySQL, di MyISAM dan InnoDB?

Pikiran yang salah yang mulai saya tulis:

Saya pikir mungkin tidak, karena mereka tidak diindeks; jika mereka disortir itu berarti mereka adalah indeks.

Ini tidak benar karena setiap kolom indeks diurutkan berdasarkan urutan kontennya sendiri, tetapi saya bertanya tentang urutan setiap baris (atau hanya beberapa kolom) dengan indeks yang sesuai.

Untuk menjelaskan, saya katakan: ini akan berguna untuk membuat rentang pemilihan baris, yang berdiri berdampingan, bersama-sama, dengan indeks mereka, lebih cepat. Misalnya, jika saya ingin select * where id >1000 and id<2000(mungkin ada kesalahan dalam sintaks MySQL, saya tidak tahu dengan baik), maka, kolom id itu sendiri dapat dibaca dari disk dengan cepat karena mungkin sel-selnya dari 1000 hingga 2000 tetap bersama di disk fisik . Tetapi konten kolom lain yang terkait dengan id 1000 hingga 2000 dapat ditulis pada tempat yang berbeda pada disk fisik. Jika mereka juga diurutkan, mereka akan dibaca lebih cepat. Saya pikir, mungkin MySQL secara otomatis mengurutkan kolom pada disk fisik, untuk kinerja operasi seperti itu.

Apakah mereka diurutkan dalam jenis database lain (PostgreSQL, dll.)?

27 Desember: Saya melihat dari 2 jawaban, bahwa dalam kasus ketika ada indeks / kunci utama berkerumun, baris sederhana itu sendiri tidak diurutkan pada disk fisik (seperti yang saya pikir mungkin / mungkin), dan bahkan indeks berkerumun adalah tidak diurutkan, jika b-tree, saya telah membaca tentang b-tree dan melihat bahwa node-nya, seperti yang saya mengerti, tinggal di tempat acak pada disk.

qdinar
sumber

Jawaban:

9

Mereka mungkin diurutkan dalam beberapa kasus. The menyortir Indeks biasanya disebut kunci pengelompokan . Jika demikian maka seluruh tabel disimpan di dalam indeks tersebut (biasanya dalam semacam struktur B-tree).

Dalam kasus lain, struktur tabel dikenal sebagai heap , baris disimpan begitu mereka datang, menghapus daun "lubang" di blok data dan lubang itu kemudian diisi dengan baris baru, sehingga bahkan "susunan penyisipan" tidak akan dipertahankan.

MyISAM menggunakan struktur tumpukan , dengan setiap baris diidentifikasi oleh offset (semacam indeks array ) ke dalam file data. Setiap indeks kemudian berisi kolom yang diindeks untuk setiap baris, diurutkan dalam urutan yang tepat dan dengan nomor offset untuk menemukan baris yang sebenarnya. Itu berarti bahwa mengakses baris dengan indeks apa pun berarti menemukan simpul kanan dalam indeks (B-tree) dan kemudian membaca offset yang tepat dari file data (pencarian acak ke bagian lain dari disk dapat terjadi ).

InnoDB menggunakan pengelompokan oleh kunci utama (atau jika tidak ada yang didefinisikan, kunci unik non-nol digunakan, atau kolom penambahan otomatis internal ditambahkan - sehingga baris selalu diurutkan entah bagaimana). Dalam hal demikian, akses oleh kunci utama adalah "langsung", ketika nilai yang tepat berada, Anda memiliki seluruh baris, tidak perlu melakukan pembacaan kedua. Indeks sekunder di sisi lain tidak dapat menyimpan offset seperti di MyISAM (karena B-tree secara dinamis menyeimbangkan dirinya sendiri, sehingga offset baris tertentu dapat berubah kapan saja) dan mereka menyimpan nilai kunci utama dari baris sebagai gantinya - jadi akses dengan kunci sekunder berarti dua pencarian B-tree di InnoDB.

MS SQL Server menawarkan opsi untuk membuat kunci utama (atau indeks lainnya) baik berkerumun atau tidak, sehingga Anda dapat memilih antara tumpukan (tidak ada indeks berkerumun) dan struktur pohon (satu indeks dikelompokkan). Semua indeks non-clustered lainnya menyimpan nilai-nilai khusus (RowID) dalam kasus tumpukan atau nilai-nilai kunci berkerumun dari baris dalam kasus CI.

PostgreSQL hanya menggunakan heap tables tetapi memungkinkan Anda menyusun ulangnya dengan beberapa indeks sesuai permintaan (Anda harus memicunya, sehingga baris-baris tersebut dipesan setelah tindakan tetapi selanjutnya menulis ke tabel dapat memecah urutan itu lagi).

TokuDB (mesin MySQL / MariaDB pihak ke-3) dapat menggunakan beberapa kunci pengelompokan pada satu tabel - secara efektif ia memelihara banyak salinan tabel, masing-masing diurutkan dengan cara yang berbeda. Itu datang dengan penalti pada menulis, tetapi TokuDB mengklaim untuk menggunakan sesuatu yang mereka sebut indeks fraktal yang seharusnya membuat penalti itu cukup kecil.

Jika Anda perlu menggunakan fungsionalitas itu untuk beberapa permintaan, Anda dapat "meniru" itu dengan membuat indeks penutup - dengan cara itu kolom-kolom yang dibutuhkan permintaan kueri Anda tersedia dalam urutan yang tepat kapan saja, tetapi sekali lagi itu berarti mempertahankan salinan yang dipesan (bagian dari ) tabel dalam indeks Anda.

jkavalik
sumber
5

Jawaban singkat dan sederhana untuk basis data secara umum adalah: tidak, urutan fisik baris dalam tabel umumnya tidak sama dengan pada beberapa indeks pada tabel itu.

Secara umum (saya katakan secara umum karena ada kasus khusus di mana itu tidak benar) tabel dan indeks adalah dua struktur fisik yang berbeda pada disk. RDBM konvensional menyimpan data sehingga nilai-nilai dari satu baris tabel (bukan kolom ) terletak bersebelahan di disk; baris itu sendiri tidak disimpan dalam urutan tertentu. Entri indeks, di sisi lain, disimpan secara berurutan; indeks b-tree tipikal berisi nilai yang diurutkan dari kolom yang diindeks (tetapi bukan kolom lain!) dan semacam penunjuk ke lokasi seluruh baris dalam tabel yang, seperti yang saya katakan sebelumnya, struktur fisik terpisah pada disk.

Yang sedang berkata, ada kasus-kasus khusus. Sebagai contoh, InnoDB MySQL menyimpan baris data aktual dalam struktur seperti indeks. Indeks dimana baris ditempatkan dalam "tabel indeks" tersebut biasanya merupakan kunci utama tabel; dan indeks semacam itu disebut indeks berkerumun . Tapi tentu saja, tabel InnoDB mungkin memiliki indeks lain dan urutan baris (yaitu, kolom baris yang termasuk dalam indeks masing-masing) dalam indeks tersebut tidak ada hubungannya dengan pemesanan baris dalam tabel itu sendiri.

zgguy
sumber