So, say for example you want to know the difference between a document store and an RDBMS then there are plenty of places to tell you. But what happens when you look in a bit deeper ?
Well, the truth is there are a lot of things the same, just named differently. Understanding one in depth can help to understand the other. So I'm going to look at the B-Tree index and how data is physically structured away from any schema.
Think of it like an upside down tree and it's easier to suss. At the very top of the tree (the root) is the entry point. Values at the opposite end (the leaf) are the actual data.
The B in B-Tree stands for balanced, and what this means is the leaf nodes are split pretty evenly. As more data gets added to the data store then the B-Tree is re-balanced automatically to give an even distribution (logically). It does this by moving data within the pages to another location. This (for the MS SQL guys) is called a page split. You can often find hundreds of these a second in busy systems. When data isn't on physically contiguous pages then this is physical fragmentation.
Physical fragmentation can be a bad thing (more so on mechanical storage) so this is why indexes need to get re-built so it can be accessed easily on the storage without too much effort.
To get to some data you need to start at the root node and work through to the leaf node. The more work you do here, the slower your query will be. If you touch lots of intermediate and leaf nodes then you are doing a lot more work in picking out the page you actually want. I like to think of this as trying to fall through the ugly tree without hitting too many branches. The more you hit, the uglier it gets.
How does this apply to various data stores ?
In MS SQL we often talk of a clustered index. This is the physical data and therefore the clustered index IS the data in the B-Tree. The order you get your data back in is defined by how this structure is built. If you build it in a specific way that the data doesn't need transforming in or out then you save on processing time and therefore make it quicker.
To get a single page, this is called a seek. When we deal with the clustered index or primary index we can get all of the data by knowing the key. If you don't have a clustered or primary index this is called a heap and is effectively like a pile of leaves that have been swept up in autumn.
To get a single page, this is called a seek. When we deal with the clustered index or primary index we can get all of the data by knowing the key. If you don't have a clustered or primary index this is called a heap and is effectively like a pile of leaves that have been swept up in autumn.
If we move to say CouchBase, data is stored in buckets. These are the same as the leaf node. It just has a different name. Your KVP key is the clustered index by a different name. The value in the Key Value Pair can be a single value or the document. MongoDB uses a DocumentID which is a 12 byte number for each document. CouchBase can allow you to have composite values to form the key.
If you add what CouchBase and MongoDB call a Seconday Index then again it uses a B-Tree. In MS SQL this is called a non clustered index. This time around it doesn't hold all of the data. It contains the data for the index but if you need more, then you need the pointer it gives you so you can go back to the B-Tree index and do a second pass using that. This in MS SQL is called a Key Lookup or RID (row identifier) lookup. You need 2 passes through the index to get all of the data.
If you don't have the right index then you need to check each leaf node or bucket. This is called a scan as you have to check them all. Doing this burns processing time and needs more IO as you need to obtain every page, read it, decide if you need it and move on to the next page of data.
If I shard my data and need to select something through a mechanism that doesn't use the shard key (say I shard by hash and I query by range) then each shard must do the same work to find the data within the shard. If I add in large quantities of data and don't use the sharding key then I burn more CPU and therefore need to introduce a more scale out strategy to compensate. If I use large quantities of data then I need more RAM which is also helped with a scale out approach to the data. It gives me different complications by doing this so I need to consider the trade offs.
One of the best things about structuring data in MS SQL is that I can have my clustered or primary index as something different to the primary key. I can have an ID as a non clustered primary key, yet my clustered index can be over various other values (say a name for example). I can choose what suits my querying best so I only need to do a single pass through. I can't do this in MySQL. Nor can I that I am aware of in CouchBase or MongoDB for example as it would mean using the value part or the document as my primary index. When you really start looking at natural and composite keys and use this flexibility you can avoid a secondary pass and therefore gain speed.
If I now add in partitioning this is done at the root node. I can put everything A to F in one partition and G to Z in others. If I need value B then I can totally ignore the other partitions (partition elimination). Again this lightens the load if done correctly and means I only need some partitions in memory so have room for other things. I'm not aware of a way of doing this in a KVP or Doc store and it can't be done in MySQL either that I am aware of.
Learning to navigate this all properly is one of the keys to unlocking the performance in a data store.
There are other types (column store and BW-Tree for example), but if you get the hang of the B-Tree structure then it all starts to make more sense.
No comments:
Post a Comment