Help with disk error "Keys not in order"

I lost access to a partition of my disk yesterday and the disk utility
said "Keys not in order"

The events:
Suspect folder was opening slowly for a few days. I was opening the
folder and it was taking a loooooong time again ( spinning wheel).
(interestingly the folder did not display the folder icon)
Eventually I tried to force the Finder to quit, but to no avail.
So I shut down the system(held boot buttion down).

Next day upon boot up the partition did not show up.
Ran disk utility and it said "Keys not in order"

What went wrong and what can I do?

Hardware:
Power Mac G4 400 AGP
Original 30gb hd and added Seagate 120gb hd partitioned to three 40gb
(effective 37gb) partitions. One partition was the one in question.

System:
OSX 10.3.9 on one of the other partitions.
Partition in question had 11gb free, rest filled with MP3s.

Any suggestions will be appreciated
--Paul

In article <181220071837295588%anon@nowhere.com>, Paul K
<anon RemoveThis @nowhere.com> wrote:

> I lost access to a partition of my disk yesterday and the disk utility
> said "Keys not in order"
>
> The events:
> Suspect folder was opening slowly for a few days. I was opening the
> folder and it was taking a loooooong time again ( spinning wheel).
> (interestingly the folder did not display the folder icon)
> Eventually I tried to force the Finder to quit, but to no avail.
> So I shut down the system(held boot buttion down).
>
> Next day upon boot up the partition did not show up.
> Ran disk utility and it said "Keys not in order"
>
> What went wrong and what can I do?

directory corruption, and more than likely, disk warrior can fix it:

<http://www.alsoft.com/DiskWarrior/index.html>