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 .

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.