Many databases use B+tree indexes, but they all differ. It's a sorted structure. The leaf pages are logically sorted so that a specific key value belongs to one page. A lookup by value reaches a single leaf page and either directly finds an entry for that value or immediately knows there's no entry with that key. When a page becomes full, it is...