Here is how I see the UI:

Search for [                    ] in [All|Title|Artist|Album]

The first idea that comes up, would be to add 3 hastables in rb-node:
{ title; ref to a node }
{ artist; ref to a node }
{ album; ref to a node }

These would be filled when the property is set, exactly the same way
that the hash of locations is filled.

Advantages:
- The implementation is rather simple
- The performances should be quite good

Inconvenients:
- Sounds rather dirty ;) 
- More RAM consumption, although i'm not sure if this is really harmful
- Might slow more the startup, cuz these hash need to be filled

won't work, it'd only work if the *exact* title/artist/album whatever
was requested ;)

seth made an impl using hashes, but it ate insane amounts of memory
and was very slow on startup.

Heh yeah you need the exact key X-|
But...
just looking at that page, it might do the job better:
http://developer.gnome.org/doc/API/2.0/glib/glib-relations-and-tuples.html

still requires the exact key :)

Allright :) 
No magic data structure able to search on a part of the value i guess 
then. Rb needs a magic algorithm both fast and not eating memory...

I've been thinking about it and the solution of a database seems 
really the bad choice to me (no solution yet, but i know what not to 
do ;)

Having a DB would force us to get it synchronized when nodes are 
added/modified/deleted. Thus we would have to get in sync the db, the 
node model and the view.... So: more problems to come and we do not 
have amount of data...

Need to think about an smart implementation... what are your plans, 
if you have any, jorn?

Implemented, thanks Olivier!

We need to get a faster algo at some point, but this bug can be closed :D