For a relational database:
A database contains 1 or more tables. Each table can have 0 (zero) or more records (rows) in it. Associated with the table is a table definition that describes the fields contained in each record. This is sometimes referred to as the table schema. The table definition can also contain 0 (zero) or more active or inactive indexes to sort or access the data with. When records are added, modified, or deleted, all of the indexes defined in the table definition are maintained to make sure that that particular record is in the correct place in all of the indexes.
Indexes can be composed of 1 or more fields. Multiple field indexes are common. For an example, if a table had the fields LastName, FirstName, MiddleInit, there may be an index for that table that sorted the records in alphabetical order based on LastName, then by FirstName and then by MiddleInit. There may be other fields that are sorted on such as record_id used primarily for record updating functions, or TotalDollarVolume (Descending) to sort the best customers to the front of the list.
There are other types of indexes in databases which are called "Hash" indexes. These indexes do not sequentially return records in any given order. They are just fast ways to access particular records. You can access a particular record very quickly if you have the record "Key" using a hash table. (The Key would be the values of the field(s) defined in the index). With Hash tables, there is no next or previous record defined. It is only a true or false type of the question "Does this record exist?" that gives a quick answer.
For non-relational databases:
Non-relational databases are generally either non-indexed, or hash-indexed. For the non-indexed values, the data is stored in the order that it was added or inserted into the database. For hash-indexed databases, value pairs are stored. For example you can save the data "815-555-1212" with the Key Value of "1234". If you access the record with the key value of "1234", the data value returned will be "815-555-1212". You could just as easily save the data "Microscope" with the key value of "Q3". If you accessed the record with the key value of "Q3", the data value of "Microscope" would be returned.
There is no order at all, implied, or otherwise derivable from a hash-indexed database. You need to know the key value in order to get the data value. Some hash-index databases may allow you to dump and load your data values, thereby giving you access to the data in a sequential form, but this is not a database user function, it is a database admin function and it does not apply to this.
There are many purposes for a Hash-index type of database.
One would be to access information for a user using the userid as the access key. It would return user information such as the user directory, permissions, encrypted password, etc for the user-id passed if the user-id existed in the database. Another purpose may be to access the information related to a particular stock such as last bid price, last offer price, high and low sales prices for the day, etc. Another purpose would be to get the connection circuit information for a telephone number. Telephone companies would need quick access to the circuit information, but would have no need to know what the previous and next values were.
Hash-indexed tables (in databases) are generally fixed in size. Some database engines have an auto-resize function to allow for more records to be added. They generally are most effective when the tables are 60% or less populated. That means that 40% of the records are not used. This is because of how hashing routines work.
How a Hash table works:
A hash table stores its records by taking the key value, and applying a mathematical formula to it to come up with a number. This number is divided by the hash table size and the result is thrown out. The remainder is used as the index into the hash table. The key value in that record is compared against the key passed to the lookup routine. If the key values match, the record is returned. If the key values don't match a collision has occurred and some collision avoidance routine is used to generate the next index. This process is repeated until the key values match. When the key values match, the record is returned. If during this search an empty record is found, a not-found status is returned. To avoid collisions, large hash tables are used.
As you can see, when hash-indexed tables are used, no record order can be implied.