Pengetahuan saya tentang database dan SQL sebagian besar berbasis di kelas universitas. Bagaimanapun, saya menghabiskan beberapa bulan (hampir setahun) di sebuah perusahaan, tempat saya bekerja dengan database.
Saya telah membaca beberapa buku dan saya telah mengambil bagian dalam beberapa pelatihan tentang database seperti MySQL, PostgreSQL, SQLite, Oracledan juga beberapa nonSQL dbs seperti kita MongoDB, Redis, ElasticSearchdll
Seperti yang saya katakan, saya pemula, dengan banyak kekurangan pengetahuan tetapi hari ini, seseorang mengatakan sesuatu, apa yang benar-benar bertentangan dengan pengetahuan pemula saya.
Biarkan saya jelaskan. Mari kita ambil database SQL dan buat tabel sederhana Persondengan beberapa catatan di dalamnya:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Sekarang, ini bagiannya, saya ingin fokus - idadalah INDEX.
Sejauh ini, saya pikir ini bekerja dengan cara ini: ketika sebuah tabel sedang dibuat, INDEXkosong. Ketika saya menambahkan catatan baru ke meja saya INDEXsedang dihitung ulang berdasarkan beberapa alghortims. Sebagai contoh:
Pengelompokan satu per satu:
1 ... N
N+1 ... 2N
...
XN+1 ... (X+1)Njadi, untuk contoh saya dengan size = 11 elementsdan N = 3akan seperti ini:
id | name | age
-----------------
1 | Alex | 24 // group0
2 | Brad | 34 // group0
3 | Chris | 29 // group0
4 | David | 28 // group1
5 | Eric | 18 // group1
6 | Fred | 42 // group1
7 | Greg | 65 // group2
8 | Hubert | 53 // group2
9 | Irvin | 17 // group2
10 | John | 19 // group3
11 | Karl | 23 // group3Jadi, ketika saya menggunakan kueri, SELECT * FROM Person WHERE id = 8ia akan melakukan beberapa perhitungan sederhana 8 / 3 = 2, jadi kita harus mencari objek ini group2dan kemudian baris ini akan dikembalikan:
8 | Hubert | 53
Pendekatan ini bekerja di saat di O(k)mana k << size. Tentu saja, sebuah alghoritme untuk mengatur baris dalam kelompok tentu jauh lebih rumit, tetapi saya pikir contoh sederhana ini menunjukkan sudut pandang saya.
Jadi sekarang, saya ingin menyajikan pendekatan lain, yang telah ditunjukkan kepada saya hari ini.
Mari kita lihat sekali lagi tabel ini:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Sekarang, kami membuat sesuatu yang mirip dengan Hashmap(pada kenyataannya, secara harfiah itu adalah Peta Hash) yang memetakan idke addressbaris dengan id ini. Katakanlah:
id | addr
---------
1 | @0001
2 | @0010
3 | @0011
4 | @0100
5 | @0101
6 | @0110
7 | @0111
8 | @1000
9 | @1001
10 | @1010
11 | @1011Jadi sekarang, ketika saya menjalankan kueri saya: SELECT * FROM Person WHERE id = 8
itu akan memetakan langsung id = 8ke alamat di memori dan baris akan dikembalikan. Tentu saja kerumitan ini O(1).
Jadi sekarang, saya punya beberapa pertanyaan.
1. Apa saja petualangan dan gangguan dari kedua solusi?
2. Mana yang lebih populer dalam implementasi basis data saat ini? Mungkin dbs yang berbeda menggunakan pendekatan yang berbeda?
3. Apakah ada di dbs nonSQL?
Terima kasih sebelumnya
PERBANDINGAN
| B-tree | Hash Table
----------------------------------------------------
---------------- one element -------------------
----------------------------------------------------
SEARCHING | O(log(N)) | O(1) -> O(N)
DELETING | O(log(N)) | O(1) -> O(N)
INSERTING | O(log(N)) | O(1) -> O(N)
SPACE | O(N) | O(N)
----------------------------------------------------
---------------- k elements -------------------
----------------------------------------------------
SEARCHING | k + O(log(N)) | k * O(1) -> k * O(N)
DELETING | k + O(log(N)) | k * O(1) -> k * O(N)
INSERTING | k + O(log(N)) | k * O(1) -> k * O(N)
SPACE | O(N) | O(N)N - jumlah catatan
Apakah saya benar? Bagaimana dengan biaya membangun kembali B-tree dan tabel Hash setelah setiap sisipan / hapus ? Dalam hal B-tree kita harus mengubah beberapa pointer tetapi dalam kasus b-tree yang seimbang perlu lebih banyak usaha. Juga dalam kasus tabel Hash kita harus melakukan beberapa operasi, terutama, jika operasi kita menghasilkan konflik .
O(1)Anda melakukannya dengan benar! Pertama-tama, sepertinya Anda menggambarkan indeks B-tree tetapi Anda memiliki beberapa kesalahpahaman. Tidak ada perhitungan (pembagian dengan 3 atau apapun), ini lebih kompleks karena pohon memiliki lebih banyak tingkatan (itu pohon, memiliki cabang besar, kecil, lebih kecil, ..., dan kemudian pergi :)Of course, an alghoritm to organise rows in groups is for sure much more complicated but I think this simple example shows my point of view.Tentu saja, saya tahu ini jauh lebih rumit. Jadi akhirnya, ketika saya mengatakan dalam kode sayaINDEXyang mana dari solusi saya ( 1 atau 2 ) yang lebih dekat dengan yang asli ini? Dan bagaimana dengan waktu yang diperlukan untuk mengakses catatan berdasarkanINDEX. Benarkah ituO(1)? Dengan indeks B-tree kedengarannya sepertiO(log2(N)). Apakah saya benar?Jawaban:
Anda pada dasarnya menggambarkan indeks B-tree dan indeks hash. Mereka berdua memiliki tempat, tetapi keduanya paling cocok untuk pekerjaan yang berbeda.
Keuntungan dan kerugian
Indeks B-tree (dan B + -tree) biasanya seimbang. Ini berarti bahwa mencari nilai akan selalu mengambil jumlah waktu yang sama di mana pun di pohon itu jatuh (O (log n)). Secara umum, jumlah level dalam pohon terbatas, sehingga cenderung menjadi "lebih luas" bukan "lebih dalam". Untuk set data kecil, biaya memelihara dan menggunakan B-tree, bagaimanapun, bisa lebih dari sekadar membaca semua baris. Indeks B-tree baik untuk set data besar, set data dengan selektivitas rendah, atau set data di mana Anda bermaksud untuk memilih berbagai objek, tidak hanya satu objek.
Tabel hash sangat bagus untuk set data kecil. Indeks hash memiliki jumlah hash bucket yang telah ditentukan, tergantung pada algoritma hashing yang digunakan. Ini karena algoritma hash yang diberikan hanya dapat menghasilkan begitu banyak hash yang unik, sehingga hanya mendapatkan "lebih dalam" bukan "lebih luas". Setelah mesin basis data menemukan ember yang tepat, itu kemudian berjalan melalui semua objek di ember itu untuk menemukan yang Anda inginkan. Dengan kumpulan data yang kecil dan sangat selektif, setiap ember berisi sejumlah kecil objek dan diselesaikan dengan cepat. Dengan set data yang lebih besar, bucket menjadi jauh lebih ramai. Jadi, jika objek yang Anda butuhkan ada di ember kecil atau dekat awal ember, ia akan kembali dengan cepat. Jika itu di ujung ember besar, dibutuhkan waktu lebih lama. Indeks tidak seimbang, sehingga kinerjanya berkisar antara O (1) hingga O (n).
Kepopuleran
Secara umum, saya paling sering berlari melintasi pohon-B. Indeks Bitmap juga merupakan pilihan lain untuk nilai-nilai dengan kardinalitas rendah (pikirkan boolean atau mungkin jenis kelamin). Ini akan bervariasi tergantung pada mesin database Anda untuk jenis indeks apa yang tersedia.
NoSQL
Database NoSQL pasti mendukung indeks. Kebanyakan mendukung B-tree atau variasi pada B-tree. Sebagian besar tampaknya mendukung indeks hash juga.
sumber
Apa petualangan dan kerugian kedua solusi? Solusi kedua tidak dapat melakukan pemindaian jangkauan. Ini bagus untuk memilih satu ID. Tetapi bagaimana jika Anda ingin id 3 hingga 8? Ia harus mengambil semua record individual yang di dunia nyata bukan hanya O (1) * 6 record untuk diambil. Dalam database produksi besar dengan indeks HashMap Anda akan mendapatkan catatan pada halaman yang berbeda, mengharuskan Anda untuk menekan disk dan membaca enam halaman berbeda ke dalam memori.
Dalam struktur B-Tree, seperti bagaimana situasi pertama Anda akan benar-benar diimplementasikan, id akan berurutan pada disk dan satu halaman kemungkinan akan menahan id 3 - 8 meningkatkan kecepatan pemindaian jangkauan akan membuat akses individu O (log n) .
Mana yang lebih populer dalam implementasi basis data saat ini? Mungkin dbs yang berbeda menggunakan pendekatan yang berbeda? Saya tidak punya pengalaman besar dalam banyak basis data yang berbeda. Saya tahu Sql Server menggunakan B-Trees kebanyakan, tetapi SQl 2014 memiliki beberapa Indeks Hash baru yang dapat Anda gunakan pada tabel tertentu. Saya mendengar banyak database No Sql dan basis data caching yang dibangun berdasarkan pengambilan catatan individual menggunakan indeks hash juga. Ini masuk akal untuk cache karena Anda ingin catatan untuk pengguna A dan tidak perlu pemindaian jangkauan.
Apakah ada di dbs nonSQL? Iya nih. Melihat sekilas pada membuat indeks dokumentasi untuk postgressql saya melihatnya mendukung kedua indeks Hash dan B-Tree serta beberapa yang lain.
sumber