Cara menyimpan informasi yang dipesan dalam Database Relasional

Saya mencoba memahami bagaimana cara menyimpan informasi yang dipesan dengan benar dalam database relasional.

Sebuah contoh:

Say I have a Playlist, terdiri dari Songs. Di dalam Database Relasional saya, saya memiliki tabel Playlists, berisi beberapa metadata (nama, pencipta, dll). Saya juga memiliki tabel yang disebut Songs, berisi playlist_id, dan info spesifik lagu (nama, artis, durasi, dll).

Secara default, ketika Lagu baru ditambahkan ke Daftar Putar, ditambahkan ke bagian akhir. Saat memesan pada Song-ID (ascending), pesanan akan menjadi urutan penambahan. Tetapi bagaimana jika pengguna harus dapat memesan ulang lagu di playlist?

Saya datang dengan beberapa ide, masing-masing dengan kelebihan dan kekurangan mereka:

1. Kolom disebut order, yang merupakan bilangan bulat . Saat lagu dipindahkan, urutan semua lagu antara posisi lama dan baru diubah, untuk mencerminkan perubahan. Kelemahan dari ini adalah bahwa banyak pertanyaan perlu dilakukan setiap kali lagu dipindahkan, dan algoritma pemindahannya tidak sepele seperti dengan opsi lainnya.
2. Kolom disebut order, yang merupakan desimal ( NUMERIC). Ketika sebuah lagu dipindahkan, ia diberi nilai floating point antara dua angka yang berdekatan. Kekurangan: Bidang desimal membutuhkan lebih banyak ruang, dan dimungkinkan untuk kehabisan presisi, kecuali kehati-hatian dilakukan untuk mendistribusikan kembali kisaran setelah setiap beberapa perubahan.
3. Cara lain adalah dengan memiliki previousdan nextbidang yang mereferensikan Lagu lain. (atau NULL untuk lagu pertama, terakhir lagu terakhir dalam daftar putar sekarang; Pada dasarnya Anda membuat daftar tertaut ). Kekurangan: Pertanyaan seperti 'temukan Lagu Ke-X dalam daftar' bukan lagi waktu konstan, melainkan waktu linear.

Manakah dari prosedur ini yang paling sering digunakan dalam praktek? Manakah dari prosedur ini yang tercepat dari basis data menengah ke besar? Apakah ada cara lain untuk mengarsipkan ini?

EDIT: Demi kesederhanaan, dalam contoh Lagu hanya milik satu Playlist (hubungan banyak-ke-satu). Tentu saja, orang juga bisa menggunakan Tabel Junction sehingga daftar lagu-adalah hubungan banyak-ke-banyak (dan menerapkan salah satu strategi di atas pada tabel itu).

Database dioptimalkan untuk hal-hal tertentu. Memperbarui banyak baris dengan cepat adalah salah satunya. Ini menjadi benar terutama ketika Anda membiarkan database melakukan tugasnya.

Mempertimbangkan:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

Dan Anda ingin pindah Beat Itke akhir, Anda akan memiliki dua pertanyaan:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

Dan itu saja. Ini berskala sangat baik dengan jumlah yang sangat besar. Coba letakkan beberapa ribu lagu dalam daftar putar hipotetis di database Anda dan lihat berapa lama waktu yang dibutuhkan untuk memindahkan lagu dari satu lokasi ke lokasi lain. Karena ini memiliki bentuk yang sangat standar:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Anda memiliki dua pernyataan siap yang dapat Anda gunakan kembali dengan sangat efisien.

Ini memberikan beberapa keuntungan signifikan - urutan tabel adalah sesuatu yang dapat Anda alasankan. Lagu ketiga memiliki order3, selalu. Satu-satunya cara untuk menjamin ini adalah dengan menggunakan bilangan bulat berturut-turut sebagai pesanan. Menggunakan daftar yang ditautkan pseudo atau angka desimal atau bilangan bulat dengan celah tidak akan membuat Anda menjamin properti ini; dalam kasus ini satu-satunya cara untuk mendapatkan lagu ke-n adalah menyortir seluruh tabel dan mendapatkan catatan ke-n.

Dan sungguh, ini jauh lebih mudah daripada yang Anda pikirkan. Mudah untuk mengetahui apa yang ingin Anda lakukan, untuk menghasilkan dua pernyataan pembaruan dan bagi orang lain untuk melihat dua pernyataan pembaruan tersebut dan menyadari apa yang sedang dilakukan.

Pertama-tama, tidak jelas dari deskripsi Anda tentang apa yang telah Anda lakukan, tetapi Anda membutuhkan PlaylistSongstabel yang berisi a PlaylistIddan a SongId, yang menggambarkan lagu mana yang termasuk daftar putar mana.

Dalam tabel ini Anda harus menambahkan informasi pemesanan.

Mekanisme favorit saya adalah dengan bilangan real. Saya menerapkannya baru-baru ini, dan itu berfungsi seperti pesona. Saat Anda ingin memindahkan lagu ke posisi tertentu, Anda menghitung Orderingnilai baru sebagai rata-rata Orderingnilai lagu sebelumnya dan lagu berikutnya. Jika Anda menggunakan bilangan real 64-bit, Anda akan kehabisan presisi pada waktu yang sama ketika neraka akan membeku, tetapi jika Anda benar-benar menulis perangkat lunak Anda untuk anak cucu, maka pertimbangkan untuk menetapkan ulang bilangan bulat bulat yang bagusOrdering nilai untuk semua lagu di masing-masing daftar putar sesekali.

Sebagai bonus tambahan, berikut adalah kode yang saya tulis yang mengimplementasikan ini. Tentu saja Anda tidak dapat menggunakannya sebagaimana adanya, dan itu akan terlalu sulit bagi saya sekarang untuk membersihkannya untuk Anda, jadi saya hanya mempostingnya agar Anda mendapatkan ide darinya.

Kelasnya adalah ParameterTemplate(apa pun, jangan tanya!) Metode ini mendapatkan daftar templat parameter yang dimiliki templat ini dari induknya ActivityTemplate. (Terserah, jangan tanya!) Kode berisi beberapa penjaga terhadap kehabisan presisi. Pembagi digunakan untuk pengujian: unit test menggunakan pembagi besar sehingga kehabisan presisi dengan cepat, dan dengan demikian memicu kode pelindung presisi. Metode kedua adalah publik dan "hanya untuk penggunaan internal; jangan meminta" sehingga kode pengujian dapat memohonnya. (Itu tidak bisa paket-pribadi karena kode pengujian saya tidak dalam paket yang sama dengan kode yang diuji.) Bidang yang mengontrol pemesanan disebut Ordering, diakses melalui getOrdering()dan setOrdering(). Anda tidak melihat SQL apa pun karena saya menggunakan Object-Relational Mapping via Hibernate.

/**
 * Moves this {@link ParameterTemplate} to the given index in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * The index must be greater than or equal to zero, and less than or equal to the number of entries in the list.  Specifying an index of zero will move this item to the top of
 * the list. Specifying an index which is equal to the number of entries will move this item to the end of the list.  Any other index will move this item to the position
 * specified, also moving other items in the list as necessary. The given index cannot be equal to the current index of the item, nor can it be equal to the current index plus
 * one.  If the given index is below the current index of the item, then the item will be moved so that its new index will be equal to the given index.  If the given index is
 * above the current index, then the new index of the item will be the given index minus one.
 *
 * NOTE: this method flushes the persistor and refreshes the parent node so as to guarantee that the changes will be immediately visible in the list of {@link
 * ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * @param toIndex the desired new index of this {@link ParameterTemplate} in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 */
public void moveAt( int toIndex )
{
    moveAt( toIndex, 2.0 );
}

/**
 * For internal use only; do not invoke.
 */
public boolean moveAt( int toIndex, double divisor )
{
    MutableList<ParameterTemplate<?>> parameterTemplates = getLogicDomain().getMutableCollections().newArrayList();
    parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
    assert parameterTemplates.getLength() >= 1; //guaranteed since at the very least, this parameter template must be in the list.
    int fromIndex = parameterTemplates.indexOf( this );
    assert 0 <= toIndex;
    assert toIndex <= parameterTemplates.getLength();
    assert 0 <= fromIndex;
    assert fromIndex < parameterTemplates.getLength();
    assert fromIndex != toIndex;
    assert fromIndex != toIndex - 1;

    double order;
    if( toIndex == 0 )
    {
        order = parameterTemplates.fetchFirstElement().getOrdering() - 1.0;
    }
    else if( toIndex == parameterTemplates.getLength() )
    {
        order = parameterTemplates.fetchLastElement().getOrdering() + 1.0;
    }
    else
    {
        double prevOrder = parameterTemplates.get( toIndex - 1 ).getOrdering();
        parameterTemplates.moveAt( fromIndex, toIndex );
        double nextOrder = parameterTemplates.get( toIndex + (toIndex > fromIndex ? 0 : 1) ).getOrdering();
        assert prevOrder <= nextOrder;
        order = (prevOrder + nextOrder) / divisor;
        if( order <= prevOrder || order >= nextOrder ) //if the accuracy of the double has been exceeded
        {
            parameterTemplates.clear();
            parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
            for( int i = 0; i < parameterTemplates.getLength(); i++ )
                parameterTemplates.get( i ).setOrdering( i * 1.0 );
            rocs3dDomain.getPersistor().flush();
            rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
            moveAt( toIndex );
            return true;
        }
    }
    setOrdering( order );
    rocs3dDomain.getPersistor().flush();
    rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
    assert getParentActivityTemplate().getParameterTemplates().indexOf( this ) == (toIndex > fromIndex ? toIndex - 1 : toIndex);
    return false;
}

Apa yang berhasil bagi saya, untuk daftar kecil di urutan 100 item adalah untuk mengambil pendekatan hybrid:

1. Kolom Urutan Sortir Decimal, tetapi dengan presisi yang cukup untuk menyimpan 0,5 perbedaan (yaitu Desimal (8,2) atau sesuatu).
2. Saat menyortir, ambil PK dari baris di atas dan di bawah tempat baris saat ini baru saja dipindahkan, jika ada. (Anda tidak akan memiliki baris di atas jika Anda memindahkan item ke posisi pertama, misalnya)
3. Posting PK dari baris saat ini, sebelumnya dan berikutnya ke server untuk melakukan pengurutan.
4. Jika Anda memiliki baris sebelumnya, atur posisi baris saat ini ke sebelumnya +5. Jika Anda hanya memiliki yang berikutnya, atur posisi baris saat ini ke berikutnya - 0,5.
5. Selanjutnya saya memiliki proc tersimpan yang memperbarui semua posisi menggunakan fungsi SQL Server Row_Number, memesan dengan urutan sortir baru. Ini akan mengubah urutan dari 1,1,5,2,3,4,6 ke 1,2,3,4,5,6, karena fungsi row_number memberi Anda tata cara integer.

Jadi Anda berakhir dengan urutan bilangan bulat tanpa celah, disimpan dalam kolom desimal. Rasanya cukup bersih. Tetapi mungkin tidak meningkatkan dengan sangat baik setelah Anda memiliki ratusan ribu baris yang perlu Anda perbarui, sekaligus. Tetapi jika Anda melakukannya, mengapa Anda menggunakan jenis yang ditentukan pengguna di tempat pertama? (Catatan: jika Anda memiliki tabel besar dengan jutaan pengguna tetapi setiap pengguna hanya memiliki beberapa ratus item untuk disortir, Anda dapat menggunakan pendekatan di atas dengan baik karena Anda akan menggunakan klausa mana untuk membatasi perubahan hanya pada satu pengguna )