I have read in a few places that MySQL is based on b-trees, among other data structures, allowing for consistent reads/writes/deletes. As a tree structure would store data based on a given key, I am curious, what is used as the key for the main b-tree structure? Is it just a hash of the table's primary key, or is there a more advanced process to compute the key associated with a given record?
My assumption was that it would be based on the primary key, as this is likely what would be used to identify a given record/row, but I haven't been able to find a definitive answer.
EDIT: This was marked as a duplicate of another question, but it is actually different. I am not asking how adding indexes works, I am asking how the general structure of a SQL database is set up BEFORE any manual indexes are placed on the table. When the table is created, how is each row stored/what is used to store it? It would seem that any query using a JOIN or asking for conditions on a field other than the primary key would take O(N) (linear) time if the key was based solely on a primary key. My research indicates that it is indexing only on primary key by default, but wanted to see if there are other data structures/ways it speeds up queries to avoid linear scans (without manual action to add indexes or other features to the db)