home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / database / theory / 310 < prev    next >
Encoding:
Text File  |  1992-07-31  |  2.5 KB  |  50 lines
  1. Newsgroups: comp.databases.theory
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!Sirius.dfn.de!chx400!bernina!neptune!nugget.inf.ethz.ch!marti
  3. From: marti@nugget.inf.ethz.ch (Robert Marti)
  4. Subject: Re: Any example of actual implementations of B-Tree's?
  5. Message-ID: <1992Jul31.141004.26043@neptune.inf.ethz.ch>
  6. Keywords: b-tree indexes indexing
  7. Sender: news@neptune.inf.ethz.ch (Mr News)
  8. Nntp-Posting-Host: nugget.inf.ethz.ch
  9. Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
  10. References:  <naran.712476183@sfu.ca>
  11. Date: Fri, 31 Jul 1992 14:10:04 GMT
  12. Lines: 36
  13.  
  14. In article <naran.712476183@sfu.ca>, naran@fraser.sfu.ca (Travers Naran) writes:
  15. |> I am writing a database program for myself and is going to be mostly
  16. |> disk-based. But now, I have the theory for B-Trees (Not binary trees, the B
  17. |> stands for something else) but no algorithms or any books that even talk about
  18. |> using it. All the books I have found so far are concerned about normalization
  19. |> and other stuff I already know about. 
  20. |> 
  21. |> How are B-Trees actually implemented? Data structures, algorithms, etc.
  22. |> Any examples by FTP or on the Net in general? Pieces of code, database sourcee
  23. |> codes, etc.
  24.  
  25. As far as I know, the B stands for Boeing, the company where Rudolf Bayer
  26. and Ed McCreight worked for when they invented this data structure.  (Of
  27. course, it could also stand for balanced, or Bayer, too ... )
  28.  
  29. Niklaus Wirth's "Algorithms and Data Structures" book contains the code
  30. for inserting, searching, and deleting entries in a B-tree which resides
  31. entirely in main memory.  (Depending on the edition, this code is written
  32. in Pascal or Modula-2.)
  33.  
  34. As for disk-based B-tree code, it becomes somewhat more tricky.  Usually,
  35. each node of a B-tree is mapped to a disk block (page).  As a result,
  36. you need to know the interface to the underlying buffer manager which
  37. will typically provide you with procedures like RequestPage, DropPage,
  38. ReadPage, WritePage, FixPage, ReleasePage, and maybe a few others.
  39.  
  40. You may want to study the code of some of the available storage systems
  41. (e.g. WiSS, the Wisconsion Storage System) or database management systems
  42. (e.g., REQUIEM, University INGRES, or Postgres), although I don't know
  43. off the top of my head which ones provide B-trees.
  44.  
  45. -- 
  46. Robert Marti                    |  Phone:    +41 1 254 72 60
  47. Informationssysteme             |  FAX:      +41 1 262 39 73
  48. ETH-Zentrum                     |  E-Mail:   marti@inf.ethz.ch
  49. CH-8092 Zurich, Switzerland     |
  50.