SQL INDEX - how it works?
What are the adventages and disadventages of both solutions?


The second solution can not perform range scans.  It is great for selecting a single ID.  But what if you want ids 3 through 8?  It has to grab all the records individual which in the real world isn't just O(1) * 6 records to retrieve.  In a large, production database with a HashMap index you would get records on different pages, requiring you to hit the disk and read six different pages into memory.

In a B-Tree structure, like how your first situation would actually be implemented, the ids would be sequential on disk and a single page would likely hold ids 3 - 8 increasing the speed of range scans will making individual access O(log n).  


Which one is more popular in current database implementations? Maybe different dbs use different approaches?


I don't have a huge experience in lots of different databases.  I know Sql Server uses B-Trees mostly, but SQl 2014 has some new Hash Indexes you can use on certain table.  I hear a lot of No Sql databases and caching databases built on retrieving individual records use hash indexes as well.  This makes sense for caches since you want the record for user A Page 11 and don't need range scans.  


Does it exist in nonSQL dbs?
Yes.  Taking a quick look at the create index documentation for postgressql I see it supports both Hash and B-Tree indexes as well as a few others.