Rockbox mail archiveSubject: Re: ID3 Database file format
Re: ID3 Database file format
From: Björn Stenberg <bjorn_at_haxx.se>
Date: Fri, 22 Oct 2004 11:03:28 +0200
Peter van Hardenberg wrote:
> PERFORMING COMPLEX QUERIES:
> Because the data is sorted and stored using fixed length records
> wherever possible, computing a query involving multiple fields is quite
> simple. Here is a breakdown of the procedure, using a search for "80s rock".
> 1) Load the song database header. Find the genre segment.
> 2) Search the binary tree for the offset/size of rock.
> 3) Load the "rock" song IDs into memory.
> 4) Search the binary tree for the offset/size of 1980s.
> 5) Load the "1980s" song IDs into memory.
> 6) Create an intersection list from the data. (Because the ids are
> already sorted, this is very fast.)
> 7) Create a playlist by loading the song filenames based on the songIDs.
This is nice, but it only solves the searching part. We also want to be able to _browse_ equally complex queries. This means we not only want to find the relevant files, we want lists of matching artists and albums too:
| |- artist1
| | |- a1album1
| | | |- a1a1song1
| | | |- a1a1song2
| | | `- a1a1song3
| | `- a1album2
| | |- a1a2song1
| | `- a1a2song2
| `- artist2
| `- a2album1
| |- a2a1song1
| `- a2a1song2
This could be solved using a few more cross-reference tables:
And cross-match them as you describe to find for example "all artists with albums with Pop songs released in 1981".
Adding another level of complexity, you hint at the desire to match against *ranges* of values ("the 1980s"), which would mean we cannot even limit ourselves to comparing against a single entry in the tables. Code complexity is increasing rapidly! :-)
This brings back my old thinking that Artist, Album and Song are "main" attributes for which browsing is solved in the database without searching. Year and Genre are "filtering" attributes which can be combined with the main attributes, but this will require a bit more cpu work and disk access.
-- Björn _______________________________________________ http://cool.haxx.se/mailman/listinfo/rockboxReceived on 2004-10-22