Tinjauan Umum yang Baik
Secara umum, Anda membuat keputusan antara waktu baca cepat (misalnya, kumpulan bersarang) atau waktu menulis cepat (daftar adjacency). Biasanya, Anda berakhir dengan kombinasi opsi di bawah ini yang paling sesuai dengan kebutuhan Anda. Berikut ini adalah beberapa bacaan mendalam:
- Satu lagi Nested Interval vs perbandingan Adjacency List : perbandingan terbaik dari Adjacency List, Materialized Path, Nested Set dan Nested Interval yang saya temukan.
- Model untuk data hierarkis : slide dengan penjelasan tradeoff yang baik dan contoh penggunaan
- Merupakan hierarki dalam MySQL : ikhtisar yang sangat baik dari Nested Set pada khususnya
- Data hierarkis dalam RDBMS : serangkaian tautan paling komprehensif dan terorganisasi dengan baik yang pernah saya lihat, tetapi tidak banyak dalam penjelasan
Pilihan
Yang saya tahu dan fitur umum:
- Daftar Adjacency :
- Kolom: ID, ParentID
- Mudah diimplementasikan.
- Simpul node murah bergerak, menyisipkan, dan menghapus.
- Mahal untuk menemukan level, keturunan & keturunan, jalan
- Hindari N + 1 melalui Common Table Expressions di database yang mendukungnya
- Nested Set (alias Modifikasi Preorder Tree Traversal )
- Kolom: Kiri, Kanan
- Nenek moyang yang murah, keturunan
O(n/2)
Bergerak sangat mahal , menyisipkan, menghapus karena pengodean yang mudah menguap
- Bridge Table (alias Closure Table / pemicu w )
- Menggunakan tabel gabungan terpisah dengan: leluhur, keturunan, kedalaman (opsional)
- Nenek moyang dan keturunan yang murah
- Menulis biaya
O(log n)
(ukuran subtree) untuk memasukkan, memperbarui, menghapus - Pengkodean yang dinormalisasi: baik untuk statistik RDBMS & perencana permintaan dalam gabungan
- Membutuhkan banyak baris per node
- Kolom Lineage (alias Path Terwujud , Enumerasi Path)
- Kolom: garis silsilah (misalnya / orang tua / anak / cucu / dll ...)
- Keturunan murah melalui kueri awalan (mis.
LEFT(lineage, #) = '/enumerated/path'
) - Menulis biaya
O(log n)
(ukuran subtree) untuk memasukkan, memperbarui, menghapus - Non-relasional: bergantung pada tipe data array atau format string serial
- Interval bersarang
- Seperti set bersarang, tetapi dengan real / float / desimal sehingga pengkodean tidak mudah berubah (langkah murah / masukkan / hapus)
- Memiliki masalah representasi / presisi desimal / float / desimal
- Varian pengkodean matriks menambahkan pengkodean leluhur (jalur terwujud) untuk "gratis", tetapi dengan menambahkan trickiness aljabar linier.
- Meja datar
- Daftar Adjacency yang dimodifikasi yang menambahkan kolom Level dan Peringkat (mis. Pemesanan) ke setiap catatan.
- Murah untuk beralih / berhenti
- Pindahkan dan hapus mahal
- Penggunaan Baik: diskusi beralur - komentar forum / blog
- Beberapa kolom garis keturunan
- Kolom: satu untuk setiap level garis keturunan, merujuk ke semua orang tua hingga ke akar, level turun dari level item diatur ke NULL
- Nenek moyang murah, keturunan, level
- Sisipkan murah, hapus, pindahkan daun
- Sisipkan mahal, hapus, pindahkan node internal
- Batas keras seberapa dalam hierarki dapat
Catatan Khusus Basis Data
MySQL
Peramal
- Gunakan CONNECT BY untuk melintasi Daftar Adjacency
PostgreSQL
- Tiga tipe data untuk Path Terwujud
SQL Server
- Ringkasan umum
- 2008 menawarkan tipe data HierarchyId muncul untuk membantu dengan pendekatan Lineage Column dan memperluas kedalaman yang dapat direpresentasikan.
sql
database
tree
relational-database
hierarchical-data
orangepips
sumber
sumber
Closure Tables
lebih unggul daripadaAdjacency List
,Path Enumeration
danNested Sets
dalam hal kemudahan penggunaan (dan saya menebak kinerja juga).Jawaban:
Jawaban favorit saya adalah apa yang disarankan kalimat pertama di utas ini. Gunakan Daftar Adjacency untuk mempertahankan hierarki dan gunakan Nested Sets untuk menanyakan hierarki.
Masalahnya sampai sekarang adalah bahwa metode penutup dari Adjacecy List ke Nested Sets sangat lambat karena kebanyakan orang menggunakan metode RBAR ekstrim yang dikenal sebagai "Push Stack" untuk melakukan konversi dan telah dianggap sebagai cara yang mahal. untuk mencapai Nirvana tentang kesederhanaan perawatan oleh Adjacency List dan kinerja Nested Sets yang mengagumkan. Akibatnya, kebanyakan orang akhirnya harus puas dengan satu atau yang lain terutama jika ada lebih dari, katakanlah, 100.000 node buruk atau lebih. Menggunakan metode push stack bisa memakan waktu satu hari penuh untuk melakukan konversi pada apa yang akan dianggap oleh MLM sebagai hierarki jutaan node kecil.
Saya pikir saya akan memberi Celko sedikit kompetisi dengan membuat metode untuk mengubah Adjacency List ke Nested set dengan kecepatan yang sepertinya mustahil. Inilah kinerja metode push stack pada laptop i5 saya.
Dan inilah durasi untuk metode baru (dengan metode push stack dalam tanda kurung).
Ya itu benar. 1 juta node dikonversi dalam waktu kurang dari satu menit dan 100.000 node dalam waktu kurang dari 4 detik.
Anda dapat membaca tentang metode baru dan mendapatkan salinan kode di URL berikut. http://www.sqlservercentral.com/articles/Hierarchy/94040/
Saya juga mengembangkan hierarki "pra-agregat" menggunakan metode serupa. MLMer dan orang-orang yang membuat tagihan bahan akan sangat tertarik dengan artikel ini. http://www.sqlservercentral.com/articles/T-SQL/94570/
Jika Anda mampir untuk melihat kedua artikel tersebut, masuklah ke tautan "Bergabung dengan diskusi" dan beri tahu saya pendapat Anda.
sumber
Ini adalah jawaban yang sangat parsial untuk pertanyaan Anda, tetapi saya harap masih bermanfaat.
Microsoft SQL Server 2008 mengimplementasikan dua fitur yang sangat berguna untuk mengelola data hierarkis:
Lihat "Model Hierarki Data Anda Dengan SQL Server 2008" oleh Kent Tegels di MSDN untuk memulai. Lihat juga pertanyaan saya sendiri: Kueri tabel yang sama rekursif di SQL Server 2008
sumber
Desain ini belum disebutkan:
Beberapa kolom garis keturunan
Meskipun memiliki keterbatasan, jika Anda dapat menanggungnya, itu sangat sederhana dan sangat efisien. Fitur:
Berikut ini contoh - pohon taksonomi burung sehingga hierarkinya adalah Kelas / Orde / Keluarga / Genus / Spesies - spesies adalah level terendah, 1 baris = 1 takson (yang sesuai dengan spesies dalam kasus simpul daun):
dan contoh data:
Ini bagus karena dengan cara ini Anda menyelesaikan semua operasi yang diperlukan dengan cara yang sangat mudah, selama kategori internal tidak mengubah levelnya di pohon.
sumber
Model Adjacency + Model Nested Sets
Saya melakukannya karena saya dapat memasukkan item baru ke pohon dengan mudah (Anda hanya perlu id cabang untuk memasukkan item baru ke dalamnya) dan juga menanyakannya dengan cukup cepat.
parent
kolomnya.lft
antaralft
danrgt
orang tua mereka.lft
lebih rendah dari simpullft
danrgt
lebih besar dari simpulrgt
dan urutkan berdasarkanparent
.Saya perlu membuat pengaksesan dan pencarian pohon lebih cepat daripada memasukkan, itu sebabnya saya memilih ini
Satu-satunya masalah adalah untuk memperbaiki
left
danright
kolom saat memasukkan item baru. baik saya membuat prosedur tersimpan untuk itu dan menyebutnya setiap kali saya memasukkan item baru yang jarang dalam kasus saya tetapi sangat cepat. Saya mendapat ide dari buku Joe Celko, dan prosedur tersimpan serta bagaimana saya menguraikannya dijelaskan di sini di DBA SE https://dba.stackexchange.com/q/89051/41481sumber
children
dandescendants
.left
danright
digunakan untuk menemukan keturunan.Jika basis data Anda mendukung array, Anda juga dapat mengimplementasikan kolom garis silsilah atau jalur terwujud sebagai array id induk.
Khususnya dengan Postgres, Anda kemudian dapat menggunakan operator yang ditetapkan untuk query hierarki, dan mendapatkan kinerja yang sangat baik dengan indeks GIN. Ini membuat menemukan orang tua, anak-anak, dan kedalaman cukup sepele dalam satu permintaan. Pembaruan juga cukup mudah dikelola.
Saya memiliki penulisan lengkap menggunakan array untuk jalur material jika Anda penasaran.
sumber
Ini benar-benar pasak persegi, pertanyaan lubang bundar.
Jika database relasional dan SQL adalah satu-satunya palu yang Anda miliki atau mau gunakan, maka jawaban yang telah diposting sejauh ini cukup. Namun, mengapa tidak menggunakan alat yang dirancang untuk menangani data hierarkis? Database grafik ideal untuk data hierarkis yang kompleks.
Inefisiensi dari model relasional bersama dengan kompleksitas dari setiap kode / solusi query untuk memetakan grafik / model hierarkis ke model relasional tidak sebanding dengan usaha jika dibandingkan dengan kemudahan yang mana solusi basis data grafik dapat menyelesaikan masalah yang sama.
Pertimbangkan Bill of Material sebagai struktur data hierarkis yang umum.
Jalur terpendek antara dua sub-rakitan : Algoritma traversal grafik sederhana. Jalur yang dapat diterima dapat dikualifikasikan berdasarkan kriteria.
Kesamaan : Apa tingkat kesamaan antara dua majelis? Lakukan traversal pada kedua sub-pohon yang menghitung persimpangan dan penyatuan kedua sub-pohon. Persentase serupa adalah persimpangan dibagi oleh serikat pekerja.
Penutupan Transitif : Jalankan sub-pohon dan jumlahkan bidang-bidang yang diminati, misalnya "Berapa banyak aluminium dalam sub-rakitan?"
Ya, Anda bisa menyelesaikan masalah dengan SQL dan database relasional. Namun, ada banyak pendekatan yang lebih baik jika Anda bersedia menggunakan alat yang tepat untuk pekerjaan itu.
sumber
Saya menggunakan PostgreSQL dengan tabel penutupan untuk hierarki saya. Saya punya satu prosedur tersimpan universal untuk seluruh basis data:
Lalu untuk setiap tabel tempat saya memiliki hierarki, saya membuat pemicu
Untuk mengisi tabel penutupan dari hierarki yang ada, saya menggunakan prosedur tersimpan ini:
Tabel penutupan didefinisikan dengan 3 kolom - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Dimungkinkan (dan saya bahkan menyarankan) untuk menyimpan catatan dengan nilai yang sama untuk ANCESTOR dan DESCENDANT, dan nilai nol untuk DEPTH. Ini akan menyederhanakan kueri untuk pengambilan hierarki. Dan mereka memang sangat sederhana:
sumber