B-Tree

PostgreSQL implements Efficient Locking for Concurrent. Operations on B-Trees (a paper in December 1981!).

B-Tree official document