Getting "error: btn: invalid key order: index nnn is greater than index nnn+1 (should be less than)"

Try running First Aid while booted into Recovery Mode. If First Aid is unable to repair the file system even in Recovery Mode, then the only option is to perform a clean install of macOS by first erasing the drive before reinstalling macOS & restoring from a backup. Unfortunately there are no third party utilities available to repair an APFS volume at this time, although the Alsoft developers are working on such support with their Disk Warrior app (they only recently began adding APFS support so it may be a year or so before I would expect it since they have no current ETA on it since they need to do a lot of testing).

Remember to have a good backup before doing anything else since a clean install will destroy all data on the drive.

How to reinstall macOS - Apple Support

TopDuck wrote:

It's been a while but I thought I'd add the final resolution here - I ended up wiping the drive and reinstalling Ventura, and yesterday upgraded to Sonoma. No usability issues, but I'll be posting in the Sonoma forum on the weird duplication of my "Macintosh HD - Data" and Macintosh HD - Data - Data" partitions. I only discovered it because Time Machine complained about a duplicate drive name.

That means you did not properly erase the drive and instead installed to the "Macintosh HD - Data" volume which then created a new "Data" volume for your home user folder marked "Macintosh HD - Data - Data". If you have a good backup, then you can try deleting the other "Macintosh HD" volumes while booted normally into macOS since it won't let you delete anything critical to the system you are currently booted.

After deleting any extra "Macintosh HD" volumes, you can rename the APFS Volume Group by using Disk Utility. Within Disk Utility, click on the "Macintosh HD - Data volumes" and rename it. You should be able to highlight the name, but I think you may be able to Right-click or Control-click on it to select "rename". Unfortunately it may not appear with a standard editing box, so it may just appear as highlighted text, but if you start typing the name it should show up. Renaming the volume group like this should also rename the macOS system volume and the "Data" volume base name.

Feel free to post a screenshot of Disk Utility showing the drive layout....you may also want to use the Terminal app and run the following command to get the drive layout as well since neither one may be easy to read the layout for this issue if you want us to confirm which item to delete and which one to highlight for renaming.

FYI, here is an Apple article for erasing a disk which explains how to use Disk Utility to delete a Volume Group when erasing the disk (has a link for instructions for Intel Macs within that article).

Use Disk Utility to erase a Mac with Apple silicon - Apple Support

The first one which is highlighted in the last screenshot is the actual Volume Group for the OS installation. It actually has a lot more hidden APFS volumes within it (Recovery, Preboot, VM, the latter is Virtual Memory aka Swap).

The ghosted out "Macintosh HD" volume is the system volume contain the macOS system files.

Next is the "Macintosh HD snapshot" volume which contains the staging area for macOS updates so it also contains a copy of the macOS system files (used to be called "Update"), however, these days I think the system toggles between those two volumes, but not certain since I haven't really examined the behavior that closely.

The last APFS volume is the "Data" volume, sometimes shown as "Macintosh HD - Data" on older versions of macOS which contains the home user folders where your important data files are stored. Technically your macOS core system configuration files & log files are stored on a hidden area of the "Data" volume as well.

The "Container disk1" is like the old time partitions, but as you can see it is more than just a simple partition in macOS. As you can see in the Disk Utility....the APFS volumes within that single Container all share the same storage pool as evidenced by each one having the same amount of Free space listed.

Glad it all worked out for you. Thanks for the update.

Edit: Here are some Apple articles regarding the new drive layout utilized by macOS 10.15+. I thought I had already provided the links:

About the read-only system volume in macOS Catalina or later - Apple Support

Signed system volume security in iOS, iPadOS, and macOS - Apple Support

What is a signed system volume? - Apple Support

You should be able to delete that volume. Notice how that volume sits at the same level as the "Macintosh HD - Data" volume that has the drop down arrow for the Volume Group (it is also ghosted out and is immediately above the line "Macintosh HD - Data snapshot").

After deleting the APFS "Macintosh HD - Data - Data" volume you unmounted (and the last item listed in the screenshot), you can rename the "Macintosh HD - Data volumes" item which has the arrow next to it to open or collapse the sub-items (3rd item from the top). Rename that item to "Macintosh HD" and it should automatically rename the sub-volumes.

Definitely make sure to have a good backup just to be safe, but since you just reinstalled macOS I'm guessing you have backups already.

I've annotated your screenshot to help make it clear....I'm assuming the red oval item is the one you unmounted.