Comments by "GH1618" (@GH-oi2jf) on "Spanning Tree" channel.

  1. I consider it to stand for "Bayer," its inventor, but it could be something else. Bayer didn't say. It definitely is not "Binary," though. Euler did not call "e" Euler's number, but everyone else does.
    4
  2. The B-tree was invented for databases residing on secondary storage devices which are much slower than the CPU and RAM. The first-order effect is to reduce the number of seeks on the disk. The secondary effects are much less important.
    2
  3. Nope. I have implemented two B-trees from scratch, never before having studied them. I first implemented a 2-3 tree, which is the minimum case of a B-tree, to get the hang of it. This was a RAM-resident data structure. Then I generalized my code to make a disk-resident B-tree. My reference was Data Structures and Algorithms, by Aho, Hopcroft, and Ullman, which I highly recommend.
    2
  4. "Modern" does not imply any particular number of years.
    1
  5. If your data structure is on secondary storage, you want a node to fill a sector, but it might be an integer multiple of sectors. The whole point of a B-tree is to reduce disk access time, but once you found a sector on disk, the following sector is available without a seek, usually. You just look at the organization of your secondary storage and make a choice. If your data structure will be RAM-resident, you might as well use a 2-3 tree, which is the minimum case of a B-tree.
    1
  6. What do you mean by "index all the data"?
    1
  7. It is a capital "B." The B-tree is a reference to Bayer, its inventor.
    1
  8. The term is "B-tree."
    1
  9. Yes, the self-balancing property is fundamental. Also, the motivation for large nodes is to reduce the number of accesses to secondary storage, the other fundamental property.
    1
  10. Is what "standard," precisely?
    1
  11. I would say a "modern" database is post B-tree. When I studied data structures in Computer Science, the B-tree had not yet made it into the curriculum. I had to learn it decades later, because it wasn't relevant to any of my work prior.
    1
  12. The B-tree is not a binary tree.
    1
  13. It is B-tree (capitalized). The "B" presumably stands for "Bayer," its inventor.
    1
  14. Given a particular application, you can usually say that one data structure is better than another, but, in general, the B-tree is an excellent data structure for many applications. A linear vector would only be better if it were RAM resident AND you hardly ever had to change it. For a database of modest size which can be kept in RAM, a 2-3 tree is an excellent solution. This is the minimum case of a B-tree.
    1
  15. "B-trees" please. Capitalized.
    1
  16. It isn't that simple. The motivation for the B-tree is to reduce the number of references to secondary storage, so you have to take into account the characteristics of secondary storage compared to primary storage.
    1
  17. The key is a scalar representing anything that fits your application. For example, if John Doe is a customer of your business, his account number might be a key in your database.
    1
  18. If your key is just a person's age, you probably wouldn't be using a B-tree, because a simple lookup table would suffice. But, in general, just think of a B-tree as a mechanism for searching keys which remains balanced while inserting and deleting keys. The links at the leaves of the tree are generally pointers to a record of data associated with a key, but could be the data if it fits within the field. My point is that the B-tree is just the mechanism for managing keys. A particular use of it will interpret the leaves in whatever way is needed.
    1
  19. The main characteristic of interest of a B-tree is that it stays balanced while doing inserts and deletes. There is no need to do cleanup. Why would you want to?
    1
  20.  @mandolinic — What is being shown here is how a classic B-tree works. If you want to design a variant, of course you are free to do so. I have implemented B-trees and I did it by the book.
    1
  21. A B-tree is balanced. It is a type of balanced tree. Its advantage is that it is always balanced as it is built. It is called a B-tree.
    1
  22. Minutes? What kind of computer are you using?
    1
  23. It's "B-tree." The point of a B-tree is to reduce accesses to secondary storage. If your B-tree resides on disk, then the node certainly should be as large as can fit in a sector, because you don't want to be reading disk space that you don't use. Whether it should be two sectors, or four, or something else, depands on the characteristics of the device and your judgment about what will work well. If your entire B-tree will reside in RAM, then you might as well use a 2-3 tree, which is the minimum B-tree.
    1
  24. I started learning computers before the B-tree was invented, so I think it is entirely appropriate to describe databases which use B-trees as "modern." The word does not imply some specified range of years, whether in computers or anything else.
    1
  25. The B-tree is an abstract data structure. The keys are just scalars, which are numbers that can be sorted, each possible key having at most one instance in the tree. Associated with the keys are links used to search the tree, or to find data associated with the keys. The interpretation of keys and links is entirely up to the implementor. A key might be a sector number on a disk, or an account number, or a telephone number, or an automobile VIN. It doesn't matter.
    1
  26. The term is "B-tree." It is important to get it right.
    1
  27. Not really. A binary tree is just a simple structure to describe and use. Note, however, that a B-tree is not a binary tree.
    1