[MUSIC] Up until now, we've discussed algorithms such as binary trees, AVL trees, arrays, and lists. And they have incredible run time performances in terms of Big O notation. But Big O notation doesn't explain everything. In fact, Big O notation assumes a uniform access time for all of our data. But in reality, uniform access time for all of our data isn't actually the case. Let's look at an example. For example, if we consider all of the Facebook profiles on Facebook, we might give a conservative estimate that there are 500 million users on Facebook. Sure there's more than that. And let's think about every single Facebook profile. We might imagine that the total amount of data that's on each profile is going to be at least five megabytes. Again another conservative estimate, because likely all the photos and all of the information we're storing on Facebook's probably going to far exceed five megabytes. Thinking of the entire amount of space that we take to store all these data, we can multiply 500 million by 5 megabytes. Doing that's going to result in us having 500 billion times 5 kilobytes, 500 trillion times 5 bytes. And I'm moving this over that's going to be 2500 trillion bytes or 2.5 petabytes of data. This is incredible amount of data, 2.5 petabytes of data it is far more than you can store in any main memory on any system. They're going to have to store some of that data on disk, and by storing on disk we know that operations going to be somewhat slower than in main memory. The goal of a BTree is to create a data structure that's going to perform extremely well in both main memory, as well as in on disk. Specifically we want to optimize the idea, that we want to make as few disk seeks as possible, so this algorithm can be as optimal as possible. And in fact, I decided the term disk seeks, but what we really can think about is any where the data stored somewhere else. This might be on the cloud somewhere, or this might be anywhere else. So let's look at how we might construct such a data structure. A BTree is constructed by having a node that contains a number of keys. I'm going to draw a node as simply a large rectangle, and as part of this node, we're going to have several keys inside of this node. And the keys can be any value, I'll assume that we're going to have integers here in the beginning. The first key might be the value of 1, the second key might be 100. Then the value 250, 400, 900 and 1,600. Each of these keys are going to have a pointer to another tree node inside of it. So between 100 and 250, this pointer right here is going to contain another node, that's going to have another set of keys. Everything in this node is going to be between the number 100 and the number 250. We're going to define every B-Tree as having an order. The order of a B-Tree refers to the size of the nodes, not the fact that the keys are in sorted order. The order of a B-Tree is the maximum number of keys that a given node can have, plus one. So for example, here's an example of a B-Tree of order 9. having 8 keys in this node. The goal of every single B-Tree is to minimize the number of network packets, disk seeks, or whatever operation we have to get at the data, so we want to minimize the seeks to reach our data. And now that we understand the motivation of the B-Tree, we want to actually understand how can implement it, and how we can build operations like insert and find in this B-Tree. So we'll do that next lecture, and I'll see you then [MUSIC]