I am using InnoDB. My Index selectivity (cardinality / total-rows) is < 100%, roughly 96-98%.
I would like to know if the columns, which are not part of the keys, are also stored in sorted order. This influences my tables' design.
Would also be interest to understand how much performance degradation in lookup I can expect when index selectivity is < 100%.
(I get these question since for InnoDB it's only mentioned that indexes are clustered and there's TID/RP stored after the index)
No, it doesn't matter for the order of the non-keyed columns.
The answer to your second is more complex - I'm going to walk through it since I think you might be misunderstanding InnoDB a little -
There are two types of indexes, primary and secondary.
The primary key index is clustered - that is, data is stored in the leaves of the B+Tree. Looking up by primary key is just one tree traversal, and you've got the row(s) you're looking for.
Looking up by secondary key requires searching through the secondary key, finding the primary key rows that match, and then looking through the primary key to get the data.
You only need to worry about selectivity of secondary (non clustered) indexes, since the primary (clustered) index will always have a selectivity of 1. How selective a secondary index needs to be varies a lot - for one; it depends on the width of the index versus the width of the row. It also depends on if you have memory fit, since if secondary keys don't "follow" the primary key, it may cause random IO to look up each of the rows from the clustered index.