There are two questions here:
1. How do you implement a pointer data structure such as a red-black tree in a database?
2. Should you implement a pointer data structure in your database to solve this problem in practice?
The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For example, to implement red-black trees in a typical relational database, you would have a table with one row for each node, with the following columns:
* an autoincrement non-nullable integer primary key column, storing the node ID
* three nullable integer columns, storing the left, right, and parent node IDs
* a non-nullable bit column, storing the red-black flag
* columns for whatever actual data is associated with each node
And then you would have a table with one row for each tree, with an integer column pointing to the root node for that tree.
As for (2): if your lists are less than a few thousand elements, it's definitely likely—as @D.W. points out—that the best way to store the ordering in a database is not to do the above. 242
Skip the pointer columns and just give your table of lists a blob column that stores that list's item IDs in order as a series of 2-byte or 4-byte ints. When your app wants to show the list, it reads the entire blob for that list; when it wants to reorder a list, it overwrites that list's blob with an entire new blob. [*]
If your lists are large enough, you might want to start profiling different options' performance. But you mention a drag-and-drop UI, and such UIs are rarely amenable to reordering lists longer than even a few dozen elements.
[*] Implementation note: If you go with this option, make sure you have another column on the items tracking which list each item belongs to, rather than just using a single autoincrement ID column. Otherwise, repeatedly creating and deleting lists could overflow your IDs even if each individual list only has a few items in it! 242