Awesome Data Structures in Open Source

A list of data structures used in Open Source projects in various languages and projects around the web. This list is primarily intended for students/developers who want to see real-world usage of various data structures, being used in production code. It is also intended for experienced developers and contributers whose deep knowledge of OSS projects would help students and beginning developers around the world get a feel for raw code, and how theory translates into practice.

All languages, frameworks, and libraries are included, as long as the link demonstrates usage/declaration of a data structure in an open source project.

Contributing To This List

Please ensure your pull request adheres to the following guidelines:

• Make an individual pull request for each suggestion.
• Add some description of the data structure used in the context of the project.
• New categories or improvements to the existing categorization are welcome!

Thank you for sharing your hard-earned knowledge!

Hash Tables

• Wget

  • Used for cookie storage. See the header file here

• PostgreSQL

  • PostgreSQL uses dynamic hashing tables. Read all about them here.

• Git

  • The version control system Git uses hashmaps and hashtables internally (Documentation) (header and main). Hashmaps are used in caches, file name hashes etc.

• MySQL

  • MySQL uses hash structure to store records - see the header.

• Recutils

  • Base memory table for storing any element.

Trees

• PostgreSQL

  • Red Black trees are used for fast storage of data in the core database engine. See the header file and main file.

• RethinkDB

  • Every RethinkDB table is represented as a B-tree. An internal node/leaf node are the basic structures used (page caches are used to store the blocks of the B-tree) where each node can have multiple children represented by offsets.

• Git

  • Git has many uses for trees - cache trees etc

• MySQL

  • Red Black trees are used in its InnoDB storage engine, for indexing primary tables. See the header and implementation

• Apache Spark

  • Apache Spark uses decision trees for classification and regression. Grok the readme here and see the actual implementation here.

• D3.js

  • This popular visualization library for javascript uses red-black trees for Voronoi geometry. See its implementation here.

• vamonos

  • This visualization library uses binary trees in Coffeescript for visualization of algorithms.

• Linux - Completely Fair Scheduler(CFS)

  • The new linux version CFS maintains a time-ordered red-black tree to maintain tasks instead of using a run queue. The self-balancing property and the O(logn) operations time help in creating an optimized scheduler.

Heaps

• PostgreSQL
  • PostgreSQL uses Binary Heaps [ see header and main ] and Pairing-Heaps [ see header and main ].

Queues

• MySQL
  • A priority-queue is used by MySQL, the base queue implementation of which is straight from the textbook - implementation.

License

This work is licensed under a Creative Commons Attribution 4.0 International License.