VietMX Staff asked 3 years ago
Think about B-Tree as a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set), but is most commonly used to implement a map (ditto for java.util.Map).
If you think about a linguistic dictionary, it’s ordered by “word”, and associated with each word is a definition. You look up a word, and get a definition.
The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query.
A typical use of B-Trees is to implement DB indexes. A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store.
A typical use in a modern filesystem is to implement directories (“folders” if you’re more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.
