Timeline for Is there a type of database that can directly recall an element given a pointer in O(1) time?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 28, 2020 at 13:53 | comment | added | user1822 | A modern database will typically need around 4 I/O operations to find the row for a given PK value regardless of the size of the table. | |
| Mar 28, 2020 at 13:37 | comment | added | ZMitton |
Thank you for the insight. How is that possible though? What does "pretty much" constant time mean? I first assumed/hoped primary key (id) may be implemented as a an address + (id * offset), but cursory research has determined that to be false.
|
|
| Mar 27, 2020 at 7:14 | comment | added | user1822 | "That means that finding a single value is doing O(log n) disk reads" - that's not true. B-Trees in relational databases are quite efficient and even for really large tables, looking up a row by a primary key is pretty much constant in time. | |
| Mar 27, 2020 at 4:06 | history | edited | Paul White♦ | CC BY-SA 4.0 |
added 420 characters in body; edited tags
|
| Mar 26, 2020 at 10:48 | answer | added | sunil | timeline score: 1 | |
| Mar 26, 2020 at 8:15 | review | Close votes | |||
| Mar 27, 2020 at 4:06 | |||||
| Mar 26, 2020 at 4:01 | review | First posts | |||
| Mar 26, 2020 at 5:52 | |||||
| Mar 26, 2020 at 3:57 | history | asked | ZMitton | CC BY-SA 4.0 |