Rhythmbox stores its music database as an XML file located in ~/.local/share/rhythmbox/rhythmdb.xml. The easiest way to reset this database is to close the Rhythmbox program, and completely remove the rhythmdb.xml file.

➜ pkill rhythmbox
➜ rm ~/.local/share/rhythmbox/rhythmdb.xml

➜ rhythmbox &

Reference: