4 ms·

I understand that B+ trees made relational databases practical. Is that true? How are they used (sorted, according to link)? How do B+ differ from B trees?

shakna 6y ago
They have some things that a relational database likes: + Fast search (log(N)) + Insert/Delete are fast (O(N) ... Most of the time) + Iteration is fast (unlike a hash map or similar) You could have a look at [0] for a deeper dive. [0] https://cstack.github.io/db_tutorial/parts/part7.html https://cstack.github.io/db_tutorial/parts/part7.html
- hyperpallium 6y ago
  Thanks, sounds like sorting is an implementation detail, and not the main benefit in itself.
  - aboodman 6y ago
    Imagine you're doing: SELECT * FROM EMPLOYEE, DEPARTMENT WHERE EMPLOYEE.DEPARTMENTID = DEPARTMENT.ID The naive thing would be to iterate employees and for each one read the corresponding department. However that would mean one disk seek per employee. Disk seeks on the rotational disks relational dbs were developed for took hundreds of ms to complete. Even today's rotational disks have seeks that take dozens of ms. So doing one seek per join result doesn't work at all. You can add caching to disguise to some extent, but that costs memory. Compare to B-Trees: You build an index on EMPLOYEE.DEPARTMENTID. That index is also a B-Tree. Because they are sorted, you can just walk both employee index and department table in parallel by id. You only need to do n/k seeks (where k is branching factor of the b-tree). You only need one record worth of caching per table (the one under the current cursor). Bonus: because the indices are sorted, it's easy to pipeline each seek after the previous to further reduced the latency of the query.
    - hyperpallium 6y ago
      Thanks, makes sense! I've once before seen comparing sorted values is faster, even when not all match. If "building an index" means it's just the indices (not all rows of the table), doesn't that indirection mean an extra seek to get the full row? (I probably have a fundamental misunderstanding here)
      - aboodman 6y ago
        You're right! But you can sort the second column of the index too. So in our case, the index would be sorted by dept id, then employee id. deptid empid 1 1 1 3 1 7 1 10 ... 2 4 2 5 2 9 ... 3 2 3 6 3 8 Now if we just do the basic thing and run through the index in order, we'll end up doing m sorted scans of the employee table, where m is the number of unique department ids. Not ideal, but if departments are large, still far better than seeking each employee individually. But we can do better: If there are relatively few departments, the database can put a cursor at the beginning of each run of them: deptid empid 1 1 <- cursor 1 3 1 7 1 10 2 4 <- cursor 2 5 2 9 3 2 <- cursor 3 6 3 8 Now the database can scan those cursors in parallel, merge sort them, and feed the result into scanning the employee id table. Now we again have a single sorted scan of the employee table, at the cost of m extra memory. This isn't a general solution. If there are zillions of departments and each one has only a handful of employees, this doesn't work. And in modern databases low-cardinality indexes like our dept_emp_id index sometimes use more specialized data structures. One of the beautiful/crazy things about working on databases is it's a product that promises an abstraction that can't actually be implemented perfectly in all cases. Databases uses all kinds of heuristics internally to decide different strategies to answer queries. And vendors are constantly refining, trying to get closer to an ideal they can never actually reach. But this particular strategy is a common and important one and an example of why B-trees were so important to early relational systems.

shakna 6y ago

They have some things that a relational database likes: + Fast search (log(N)) + Insert/Delete are fast (O(N) ... Most of the time) + Iteration is fast (unlike a hash map or similar) You could have a look at [0] for a deeper dive. [0] https://cstack.github.io/db_tutorial/parts/part7.html https://cstack.github.io/db_tutorial/parts/part7.html

hyperpallium 6y ago
Thanks, sounds like sorting is an implementation detail, and not the main benefit in itself.
- aboodman 6y ago
  Imagine you're doing: SELECT * FROM EMPLOYEE, DEPARTMENT WHERE EMPLOYEE.DEPARTMENTID = DEPARTMENT.ID The naive thing would be to iterate employees and for each one read the corresponding department. However that would mean one disk seek per employee. Disk seeks on the rotational disks relational dbs were developed for took hundreds of ms to complete. Even today's rotational disks have seeks that take dozens of ms. So doing one seek per join result doesn't work at all. You can add caching to disguise to some extent, but that costs memory. Compare to B-Trees: You build an index on EMPLOYEE.DEPARTMENTID. That index is also a B-Tree. Because they are sorted, you can just walk both employee index and department table in parallel by id. You only need to do n/k seeks (where k is branching factor of the b-tree). You only need one record worth of caching per table (the one under the current cursor). Bonus: because the indices are sorted, it's easy to pipeline each seek after the previous to further reduced the latency of the query.
  - hyperpallium 6y ago
    Thanks, makes sense! I've once before seen comparing sorted values is faster, even when not all match. If "building an index" means it's just the indices (not all rows of the table), doesn't that indirection mean an extra seek to get the full row? (I probably have a fundamental misunderstanding here)
    - aboodman 6y ago
      You're right! But you can sort the second column of the index too. So in our case, the index would be sorted by dept id, then employee id. deptid empid 1 1 1 3 1 7 1 10 ... 2 4 2 5 2 9 ... 3 2 3 6 3 8 Now if we just do the basic thing and run through the index in order, we'll end up doing m sorted scans of the employee table, where m is the number of unique department ids. Not ideal, but if departments are large, still far better than seeking each employee individually. But we can do better: If there are relatively few departments, the database can put a cursor at the beginning of each run of them: deptid empid 1 1 <- cursor 1 3 1 7 1 10 2 4 <- cursor 2 5 2 9 3 2 <- cursor 3 6 3 8 Now the database can scan those cursors in parallel, merge sort them, and feed the result into scanning the employee id table. Now we again have a single sorted scan of the employee table, at the cost of m extra memory. This isn't a general solution. If there are zillions of departments and each one has only a handful of employees, this doesn't work. And in modern databases low-cardinality indexes like our dept_emp_id index sometimes use more specialized data structures. One of the beautiful/crazy things about working on databases is it's a product that promises an abstraction that can't actually be implemented perfectly in all cases. Databases uses all kinds of heuristics internally to decide different strategies to answer queries. And vendors are constantly refining, trying to get closer to an ideal they can never actually reach. But this particular strategy is a common and important one and an example of why B-trees were so important to early relational systems.