Apa teknik pengindeksan data yang paling efisien

10

Seperti yang kita semua tahu, ada beberapa teknik pengindeksan data, menggunakan oleh aplikasi pengindeksan terkenal, seperti Lucene (untuk java) atau Lucene.NET (untuk .NET), MurMurHash, B + Tree dll. Untuk No-Sql / Obyek Oriented Database (yang saya coba tulis / mainkan sedikit dengan C #), teknik mana yang Anda sarankan?

Saya membaca tentang MurMurhash-2 dan komentar khusus v3 mengatakan Murmur sangat cepat. Juga Lucene.Net memiliki komentar bagus tentang itu. Tapi bagaimana dengan jejak memori mereka secara umum? Apakah ada solusi efisien yang menggunakan lebih sedikit jejak (dan tentu saja jika lebih cepat lebih disukai) daripada Lucene atau Murmur? Atau haruskah saya menulis struktur indeks khusus untuk mendapatkan hasil terbaik?

Jika saya mencoba menulis sendiri, lalu apakah ada skala yang diterima untuk pengindeksan yang baik, sekitar 1% dari data-node, atau 5% dari data-node? Setiap petunjuk yang bermanfaat akan dihargai.

sihirbazzz
sumber

Jawaban:

10

Saya pikir Anda mengacaukan beberapa hal dalam pertanyaan Anda. Lucene (saya tidak tahu apa-apa tentang Lucene, NET, tapi saya kira sama) adalah perpustakaan yang digunakan untuk menganalisis, membagi token, dan menyimpan dokumen agar dapat meminta dan mengambilnya nanti. Lucene memiliki model yang cukup tua namun efektif, menggunakan pohon terbalik untuk menemukan dan mengambil dokumen. Tanpa perincian lebih lanjut, semua dokumen dibagi dalam token (istilah), dan untuk setiap istilah dipertahankan struktur data, yang menyimpan semua dokumen yang berisi istilah yang diberikan. Sebagai struktur data dapat digunakan BTree, tabel hash dan dalam revisi utama terbaru Anda bahkan dapat memasukkan struktur data Anda sendiri.

BTree (lihat halaman Wikipedia untuk perincian lebih lanjut), adalah sejenis struktur data pohon, yang sesuai untuk bekerja dengan potongan besar data dan sering digunakan untuk menyimpan struktur seperti pohon pada disk. Untuk in-memory, pohon lain berkinerja lebih baik.

Murmur hash (lihat halaman Wikipedia untuk detail lebih lanjut), adalah keluarga fungsi hash yang digunakan dalam tabel hash. Implementasi dari tabel hash tidak penting, itu bisa menjadi implementasi rantai standar atau skema penanganan hash terbuka yang lebih maju. Idenya adalah bahwa tabel hash memungkinkan seseorang untuk mendapatkan kunci dengan cepat, dari set kunci yang tidak berurutan, dan dapat menjawab tugas-tugas seperti: apakah ini bagian kunci dari set kunci ini? yang merupakan nilai yang terkait dengan kunci ini?

Sekarang kembali ke masalah utama Anda. Anda memiliki satu perpustakaan (Lucene) dan untuk struktur data, kedua struktur data digunakan di Lucene. Sekarang Anda melihat bahwa tidak mungkin untuk menjawab pertanyaan Anda dalam istilah ini karena tidak dapat dibandingkan.

Namun, mengenai jejak Anda dan bagian kinerja dari pertanyaan. Pertama-tama Anda harus tahu jenis operasi apa yang perlu Anda terapkan.

Apakah Anda hanya perlu mendapatkan nilai untuk kunci, atau apakah Anda perlu menemukan semua elemen dalam rentang? Dengan kata lain apakah Anda perlu memesan atau tidak? Jika Anda melakukannya, maka pohon dapat membantu. Jika tidak, dari tabel hash, yang lebih cepat bisa digunakan sebagai gantinya.

Apakah Anda memiliki banyak data yang tidak sesuai dengan memori? Jika ya daripada solusi berbasis disk akan membantu (seperti BTree). Jika data Anda sesuai dengan memori, daripada menggunakan solusi in-memory tercepat dan gunakan disk hanya sebagai penyimpanan (dengan struktur yang berbeda, jauh lebih sederhana).

rapaio
sumber
Terima kasih banyak Rapaio :) Poin yang Anda berikan kepada saya sangat berguna dan mendapatkan sesuatu yang lebih jelas .. Karena saya seorang pengembang .NET dan ingin tahu di dataran C (saya mulai belajar) dan tambahan baru, cepat, dapat diandalkan, dapat ditingkatkan tentu saja sepenuhnya terkendali -dalam jangka pendek: sangat bersemangat- teknik..Jadi saya perlu belajar sangat banyak..Untuk belajar, saya mencoba membaca begitu banyak dokumen tetapi karena Anda bisa menebak saya berada di garis start .. Saya tidak tahu bahwa BTree memiliki kelebihan pada disk (Di dunia. Net, begitu banyak penulis menjelaskannya seperti: Struktur data hierarkis seperti Linked-List..Tidak Lagi!) Terima kasih banyak lagi
sihirbazzz
Dan jika Anda mengizinkan saya, sampai ada penjelasan / jawaban kualitas yang lebih tinggi daripada milik Anda, saya ingin menerima ini sebagai jawaban .. Dan BTW, Lucene.NET adalah implementasi .NET dari Java's Lucene
sihirbazzz