Creating music library database that is easily updatable

Question

I am writing a music player for the sake of learning. I am not sure how to design the database part of it (I want to create it myself, not use some version of MySQL). My best idea so far is to create a "song" class, with filename, title, artist, album, etc. variables. Then I would have an array of "songs". This works well enough, but when it comes to updating, it seems horrendous. To add one song to the library, it has to be checked against every other song. With a significantly large library and/or a large update, this becomes undesirable (n^2?).

I know a little bit about data structures. I was thinking some sort of hashing function could speed this up, but my knowledge of hashing is very limited.

My question: what is a better design for a music library database and updating said database?

Thanks,

Tim

Edit: I am programming in Python.

Answer 1

to create your own you may want to have a look at b+ tree structures or similar, that way you can insert and search the list very fast.

here's a link to wikipedia to give a little info on them http://en.wikipedia.org/wiki/B%2B_tree

Direct from wikipedia:

For a b-order B+ tree with h levels of index:

* The maximum number of records stored is n = bh
* The minimum number of keys is 2(b / 2)h − 1
* The space required to store the tree is O(n)
* Inserting a record requires O(logbn) operations in the worst case
* Finding a record requires O(logbn) operations in the worst case
* Removing a (previously located) record requires O(logbn) operations in the worst case
* Performing a range query with k elements occurring within the range requires O(logbn + k) operations in the worst case.

Answer 2

If you have good indexes, I've found that you generally can't beat what relational databases have to offer in this respect. I have less experience with MySql, but I would be that the fastest way to do what you are saying is to in fact query the database for it.

Also, as a good rule of thumb, focus on functionality not performance unless you really need to. Solve that problem when you get there.

Answer 3

Identify some sort of "primary key" or unique identifier for every song. use that as the key in a dictionary data structure and set the song object as the value

this way if you insert the same song again, it will be overwritten.

For example in Java, we can use a HashMap. with filename as the key and song object as the value. So if we attempt to enter the same filename again, it will be ovewritten

Answer 4

Your question seems to be in two parts, one about creating an index, which John answered well, if concisely, but the other is that your approach may be flawed in your assumption.

You may want to look at how ITunes or Windows Media player breaks up the song, so you will have artist -> album -> song. If you need to add a new song, just look at the artist and album first, as the same artist may have remade a song on several albums, and then these should be added to the database.