I don't think the indexing would slow it down too much, especially once the initial indexing is done and cached. It would accomodate all users better if there was simply an option to "Organize Library by Folder Stucture" or "Organize Library by Tag Info". Organizing by tags allows for much more flexibility (sorting by genre or by song rating, also a feature that is still missing). The more flexible the software the better. Let the user choose how they would like their music organized.
-hogfan