4 ms·
why use b trees if the keys are out of order?
by tonymet 3y ago
why use b trees if the keys are out of order?
- emmanueloga_ 3y agoDBs default to B-Trees even for synthetic primary keys because range queries are almost always necessary, for instance, if you want to paginate records. Some DBs also include a hash map index in addition to B-Trees, for instance Postgres [1], but still use B-Trees for primary keys. Sqlite3 doesn't support Hash indexes. There's a very short chapter in "Modern B-Trees Techniques" [2] that compare B-Trees with Hash indexes: * Durability schemes are simple and robust for b-trees, not so for hash maps. * Ordering has advantages for concurrency control by means of key range locking. * "Very few database implementation teams find hash indexes among the opportunities or features with a high ratio of benefit and effort, in particular if B-tree indexes are required in any case in order to support range queries and ordered scans." -- 1: https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I... 2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf https://w6113.github.io/files/papers/btreesurvey-graefe.pdf
- tonymet 3y agovery nice thanks