TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 15.1 - Goodrich, Tamassia, Goldwasser
This chapter provides knowledge of b trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | B-Trees 3/29/14 21:37 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 B-Trees © 2014 Goodrich, Tamassia, Goldwasser B-Trees 1 Computer Memory q q q q In order to implement any data structure on an actual computer, we need to use computer memory. Computer memory is organized into a sequence of words, each of which typically consists of 4, 8, or 16 bytes (depending on the computer). These memory words are numbered from 0 to N −1, where N is the number of memory words available to the computer. The number associated with each memory word is known as its memory address. © 2014 Goodrich, Tamassia, Goldwasser B-Trees 2 1 B-Trees 3/29/14 21:37 Disk Blocks q q q q q Consider the problem of maintaining a large collection of items that does not fit in main memory, such as a typical database. In this context, we refer to the external memory is divided into blocks, which we call disk blocks. The transfer of a block between external memory and primary memory is a disk transfer or I/O. There is a great time difference that exists between main memory accesses and disk accesses Thus, we want to minimize the number of disk transfers needed to perform a query or update. We refer to this count as the I/O complexity of the algorithm involved. © 2014 Goodrich, Tamassia, Goldwasser B-Trees 3 (a,b) Trees q q q q To reduce the number of external-memory accesses when searching, we can represent a map using a multiway search tree. This approach gives rise to a generalization of the (2,4) tree data structure known as the (a,b) tree. An (a,b) tree is a multiway search tree such that each node has between a and b children and stores between a − 1 and b − 1 entries. By setting the parameters a and b appropriately with respect to the size of disk blocks, we can derive a data structure that achieves good .
đang nạp các trang xem trước
