Foundations of Data Intensive Applications

CHAPTER 4Data Structures

Every program that does meaningful work deals with data structures. Whether it is a large-scale distributed application or a serial program running in the cluster, we can find data structures everywhere. The simplest data types we use are primitive types such as integers and doubles. Computers are designed to work on such fundamental data by loading them into special hardware units inside CPUs called registers wherein they make decisions and perform arithmetic operations.

Utilizing simple primitive types in computing is an efficient and well-documented endeavor these days. Compilers supply excellent support to optimize operations involving them. But a complex program cannot rely solely on just simple types to meet its data needs. To represent complex data, composite types are created from their less complicated brethren. Examples of such are present in any programming language. In C we program with structs, while in Java or C++, we program classes to create composite types.

An array is another composite data structure widely used in computing. An array has multiple values of the same type in a contiguous space in memory. The individual value of an array can be accessed using an index and can be of multiple dimensions, making it extremely efficient.

When we deal with substantial amounts of data, we need to use data structures that can hold them as composite forms. It all boils down to how efficient a data structure is in terms of access speed and storage. ...