That's either a disk on it's way out or something has been corrupted and the OS is having problems mounting the drive.
Do you have your system disk? If so, you could try booting into is by holding the C key while booting and run Disk Utility, then do a permissions repair and a disk repair if you can.
What fsck command did you enter? fsck -f ? If not then you should try that too.
If you can get into single-user mode then you can run the following command to repair permissions:
sudo diskutil repairPermissions /
Issue solved; no physical errors.
These are what I did:
First I analyzed where the error occurred :
...
** Checking catalog file.
Invalid index key
(4, 20220)
Invalid node structure
(4, 38065)
The volume SSD could not be verified completely.
...
fsck stops while scanning catalog files. Let's try reading fsck_hfs user manual by executing man fsck_hfs for clues.
...
-R flags Rebuilds the requested btree. The following flags are supported:
a Attribute btree
c Catalog btree
e Extents overflow btree
...
Let's try rebuilding catalog btree then. fsck_hfs -Rc /dev/rdisk0s2
Results: fsck does not stop at catalog file check anymore, and the Invalid index key error disappeared, revealing more errors ( clues! ).
** Checking extents overflow file.
Incorrect block count for file Cache.db-wal
(It should be 114 instead of 119)
** Checking catalog file.
Missing thread record (id = 30291961)
Incorrect number of thread records
Incorrect number of thread records
** Checking multi-linked files
** Checking catalog hierarchy.
Invalid directory item count
(It should be 221 instead of 244)
Invalid volume file count
(It should be 1318081 instead of 1318117)
** Checking extended attributes file.
Invalid node structure
The volume SSD could not be verified completely.
fsck now stops when checking extended attributes file. Let's try rebuilding the attributes btree with fsck -Ra /dev/rdisk0s2.
Result(s): All errors, except Invalid node structure disappeared after the first repair attempt. It shows several invalid nodes, then attempts the second repair, and rechecks. It still shows some invalid nodes, but even less then before.
However the fsck stops with a message saying that it stops making repair attempts after 3 check failures. I ran fsck -Ra /dev/rdisk0s2 again. It attempts to repair again, then rechecks. No invalid node structure error shows up!
It now makes Invalid volume free blocks count, Invalid volume file count, and Invalid volume directory count errors, but it doesn't stop yet!
After yet another attempt of repair, fsck finished without any errors.
Shut down. Boot normally without entering single user mode. And it works!
Problem solved by running fsck several times, rebuilding catalog btree, and attribute btree several times.
Best Answer
Finally I found a serious hardware error (failure of main board) was preventing installation of Yosomite. The reason I saw Virtual Box error was just a matter of chance, it printed out the lost error message before the computer crashed due to the main board error