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
Figured it out. I'd changed my keyboard layout to Dvorak which apparently isn't honored at boot, defaulting to QWERTY. I pressed Cmd+O (where the S would've been) and it worked.