Database Design - 'Lists' storage I'm "about" to implement a feature on one of my apps which requires storing a lot of data (PlayLists).

Assume the following scenario: 


A user can have multiple playlists
These playlists have up to 500k entries (maybe even more)
I must be able to get, remove, re-sort or query the whole playlist or by using indexes
Currently a playlist for each user; but
I'm about to implement a feature that will allow users to have more than 1 playlist.
About 3500 entries per playlist. Some can go as high as 590k.


Playlist entries are represented by the following class:

public class Item {
  private Long owner; // User
  private String data;
  private String name;
  private String author;
  private int index; // Index of this item on the list
}


TL;DR: List&lt; Item &gt; for every user (more than 1 per user) where this list can extend to 500k+ entries.

Currently, I have SQL-based storage for this, however, it's slow as heck, specially when I need to shift indexes - slow up to the point of my db driver thinking that the connection failed and leaked.

To explain "shift indexes": Let's say I'm removing an item at the 3rd index (i = 3), this means that all other items after it need to shift one index down, so I can later on request index 3 and get the item that was previously index 4.

Currently, I decrement the column value Order for that playlist for all elements after the one I deleted.

Current PlayList Items Table design

Id (Ordering/Index) | PlayList (Id) | Owner (User) | Name | Author | Data


Question

Which would be a better/more efficient way of storing this kind of "bulk" data, while still being able to query and modify it?

I'm ok with changing/implementing a new database software for this kind of data, since it's really big (I currently use Redis and MariaDB). However, I would love to avoid having to.
User has >1 playlist

The Answer by Vérace is correct except that it skipped the fact that each user may have more than one playlist.

So here is a diagram of my table design. I changed one column name to "sort_order" as the name “index” in a database and in programming will cause all kinds of confusion.

Basically I suspect you are failing to notice the 'list' in 'playlist', conflating each person's list of their favoritesfrom the full list of possible choices. Each playlist is a collection of references to the desired items (songs, books, or whatever your matter is  — not clear in the Question). 



Performance

As for your performance issue when inserting a new/changed row amongst the existing rows’ sort-order  numbers, you can dramatically reduce the frequency of this chore.

Increment your sort-order value by a hundred or by a thousand or by a million rather than by one. You can insert a new row by assigning a sort-order number in between the numbers of existing rows without any shifting. You only need to do a full shift when 99 or 999 or 999,999 rows happen to have already been inserted between the incremented rows. Until then you may need to do mini-shifts when clumps appear with the in-between numbers, but on small subset of rows, &lt;100 or &lt;1,000 or &lt;1,000,000. 

If you need to show sequential 1, 2, 3… numbers to user, let the database create these numbers dynamically as part of your SELECT statement.