On one side, you will keep a table of four columns, that lists all music descriptors as tuples stored in rows.
On the other side, you will maintain four B-trees that will index each of the columns. The records associated with the keys will contain row numbers in the table.
When you insert a row, be sure to update all four search indexes.
When you delete a row, be sure to delete all four fields in all four search indexes, making sure to refer to the same row every time.
To avoid wasting space in the table due to deletions, you can arrange the deleted rows as a linked list in the table, so that any new row can overwrite a deleted one.
Hope you will understand my overly concise description