Introduction
This source code (as part of the demo project) creates and uses a BTree database. It
implements the following features:
• create database
• insert/update record
• delete record
• search for keys (exact match or sort-of wildcard)
• traversal
• sequential forward and reverse record access
• user-specified fixed size records and fixed size keys
• custom comparison and traversal callbacks.
Background
A while ago, I started developing a system that would allow people to chart
(Australian) stock market movements nicely and simply and in a user-friendly
fashion (shameless plug: [Link] ). Obviously, a large part of the
client side of the system would be the storage of stock movements on the local
machine. People need to be able to look at their charts without having to download
large amounts of data every time they open a window. Programmatically, it makes
sense if these movements can be retrieved in date order, since plotting stock
movements on a chart window requires the data to be presented in date order. I
needed to be able to retrieve them rapidly, too. Bear in mind that with the data
package available with the download, some securities date back to 1980.
After a lot of mucking around, I eventually decided to write database functionality
that I could use (not GPL'd, not hideously expensive). See the Points of Interest for a
full discussion of this process.
Contents and structure of BTree DB
Before getting into the tree itself, let's have a look at what makes a tree.
Smart pointers
If you don't know about smart pointers, now would be a really good time to check
them out. Look here for the article I used as a base for my smart pointers. What
they do is let you copy pointers around, manage their own reference counting, and
ensure that objects are deleted when the last reference to the object is released or
goes out of scope.
The objects internal to the database use smart pointers a lot because ... well, it's
just so darn convenient.
The DbObj Class
A DbObj is a generic chunk of data. To create one, you invoke a constructor,
providing a pointer to some data, and the data size. There are a few other
constructors that allow you to create DbObjs of various types without having to
worry about sizes. These include constructors for std::strings, numbers and other
DbObjs. Note that these objects make a copy of your data, so you can't expect to
create the DbObj, change your original data and expect the changes to be reflected
in the DbObj. Note also that the DbObj doesn't contain any information about the
type of data stored.
The code deals with smart pointers to DbObj objects. You create DbObjs, pass them
to the BTreeDB, and forget about them. Or, get one back from the BTreeDB and
don't worry about explicitly deallocating it. The reference counting infrastructure
takes care of it.
DbObj objects are used to specify data that is to be inserted into the BTreeDB, and
also keys that are used to look up records in the BTreeDB.
In all the sample code below, I'm working with a record structure that is made up of
the following:
const size_t keyLen = 12;
const size_t dataLen = 28;
struct SampleKey
{
unsigned char key[keyLen];
};
struct SampleData
{
unsigned char data[dataLen];
};
struct SampleRecord
{
SampleKey key;
SampleData data;
};
To create a DbObj containing objects like this, you would do the following:
SampleRecord sr;
memset(&[Link], 'K', keyLen);
memset(&[Link], 'D', dataLen);
DbObjPtr pRec = new DbObj(&sr, sizeof(SampleRecord));
The TreeNode Class
A BTree contains a multi-level hierarchical collection of tree nodes (i.e., a tree).
These nodes contain a series of records, and references to child nodes. The records
in the node are stored as DbObjs as mentioned above, while the children are stored
as a list of smart pointers to TreeNode objects.
These are the chunks that get read from and written to the disk. They aren't loaded
until they are actually required.
Working with the BTreeDB
Creating a BTreeDB
To create a BTreeDB object, you invoke the constructor (duh!):
BTreeDB db(fileName, sizeof(SampleRecord), sizeof(SampleKey), minDegree);
The first parameter (fileName) is a const char* that points at a buffer containing
the name of the file. If the file doesn't exist, it's created. If the file does exist, it's
going to be used as a database file containing valid data. Note that the constructor
doesn't open the file. It just initializes the data members. The second parameter is
the size of the record (in bytes) to be stored in the database. The third parameter
allows you to specify how many of these bytes are to be interpreted as the key. The
fourth parameter is the tree's minimum degree, usually referred to in the text as t. A
tree node can hold as many as 2t - 1 keys, but may hold no fewer than t .
Not shown above is a 5th parameter for the constructor. You can provide your own
comparison function if your records require something other than a binary
comparison when it comes to sorting. The default comparison is a simple memcmp
using the first keyLength bytes of the two data objects being compared.
Opening a BTreeDB
[Link]()
If the file given in the constructor doesn't exist, it is created and initialized to handle
the record and key sizes provided in the constructor. If the file already exists, the
values provided are compared with what is already in the file, and database doesn't
open if they disagree.
This method will return false if it fails to open the database for any reason.
Reasons for failure include:
• database file locked by another process
• size and minDegree parameters not provided in constructor AND file doesn't
yet exist
• inability to create the file if creation is required
• inability to read header information from the file if the file already exists.
Yes, I could have made the open function return an error code, but I didn't. Maybe
later.
Inserting data into a BTreeDB
This is just a case of creating DbObjs that you want to insert, and then inserting
them.
for (int i = 0; i < iterLimit; i++)
{
SampleRecord sr;
makeRecord(&sr); // This just fills in the sample record
DbObjPtr pObj = new DbObj(sr, sizeof(SampleRecord));
[Link](pObj);
}
You'll have to make sure that you provide a record that is the correct size. The put
method will return false if this not the case.
This method is also used for updating existing records. note that the BTreeDB
doesn't allow you to insert multiple records that have the same key. If you "put" any
record with the same key as an existing record, the existing one will be overwritten.
Retrieving data from a BTreeDB
Create a DbObj containing the key, and then ask for the record.
SampleKey sk;
memset(&sk, 'K', sizeof(SampleKey));
DbObjPtr pKey = new DbObj(&sk, sizeof(SampleKey));
DbObjPtr pRec;
if ([Link](pKey, pRec))
{
SampleRecord sr;
assert(pRec->getSize() == sizeof(SampleRecord));
memcpy(&sr, pRec->getData(), pRec->getSize());
}
Removing data from a BTreeDB
For all the time it took to get this functionality right, using it is quite simple.
SampleKey sk;
memset(&sk, 'K', sizeof(SampleKey));
DbObjPtr pKey = new DbObj(&sk, sizeof(SampleKey));
[Link](pKey);
Other operations on a BTreeDB
There are examples in the code about how to traverse the BTreeDB, how to do "like"
searches (where the search key is smaller than the actual record key size), moving
forwards and backwards through the tree and a few other things possibly unique to
my situation.
BTreeDB Wrappers
I use wrappers to provide structure to a given database. (I don't know where I found
the Singleton class ... [have to insert link here]).
class HistoryDB
{
static const int _dbMinDegree = 49;
friend class Singleton<HistoryDB>;
public:
struct HistoryKey
{
byte exchange;
char security[10];
ushort moveDate;
byte padding[3];
};
struct HistoryItem
{
int openPrice; // Opening price in currency units
// (implied by Exchange context)
int highPrice; // High price in currency units
// (implied by Exchange context)
int lowPrice; // Low price in currency units
// (implied by Exchange context)
int closePrice; // Closing price in currency units
// (implied by Exchange context)
llong tradeVolume; // Volume of trades for the trading day
byte intraday; // 0 = this is an EOD value,
// 1 = intraday progressive value.
byte padding[7];
};
struct HistoryRecord
{
struct HistoryKey key;
struct HistoryItem item;
};
private:
static int _compareHR(const DbObjPtr& pObj1, const DbObjPtr& pObj2)
{
HistoryKey* k1 = (HistoryKey*)pObj1->getData();
HistoryKey* k2 = (HistoryKey*)pObj2->getData();
int ret = k1->exchange != k2->exchange;
if (ret == 0)
{
ret = strcmp(k1->security, k2->security);
if (ret == 0)
{
ret = k1->moveDate - k2->moveDate;
}
}
return ret;
}
private:
HistoryDB(void)
{
GlobalData& gd = GlobalDataS::instance();
string fileName = [Link]() + "[Link]";
_db = new BTreeDB(fileName,
sizeof(HistoryRecord),
sizeof(HistoryKey),
_dbMinDegree,
_compareHR);
if (!_db->open())
{
_db = (BTreeDB*)0;
}
}
public:
BTreeDBPtr& getDB() { return _db; }
private:
BTreeDBPtr _db;
};
typedef Singleton<HistoryDB> HistoryDBS;
Given the class above, I can do the following:
HistoryDB& hdb = HistoryDBS::instance();
BTreeDBPtr pdb = [Link]();
HistoryDB::HistoryRecord hr;
DBOBJVECTOR dbMoves;
memset(&hr, 0, sizeof(hr));
strcpy([Link], stockCode);
DbObjPtr pKey = new DbObj(&hr, sizeof(hr));
NodeKeyLocn locn = pdb->search(pKey);
if ((TreeNode*)[Link] != 0)
{
DbObjPtr pRec;
while (pdb->seq(locn, pRec))
{
memcpy(&hr, pRec->getData(), sizeof(HistoryDB::HistoryRecord));
if (0 != memcmp(pRec->getData(),
pKey->getData(),
sizeof([Link]) + sizeof([Link])))
{
break;
}
dbMoves.push_back(pRec);
}
}
Caveats
This is not thread-safe code ... I protect access to the database using my own mutex
in my application.
You need to be aware of when you open and close databases, and when they are
flushed to disk. There are aspects of this that I haven't fully explored, but I know
that I should be releasing memory (TreeNodes) more frequently than I do. If this is
not done, you'll end up with the entire database in memory. While it's really good for
performance on small databases, it may not be appropriate for larger databases.
At present, it suits what I'm trying to do.
Points of Interest
My first attempt at implementing a database simply had one file per security, with
the data stored sequentially. For ANZ, there was a file named [Link], for CBA there
was a file named [Link], and so on. That was fine, since there are less than a
couple of thousand securities on the ASX (Australian Stock Exchange). As the project
grew, and I started incorporating options, I had to start putting these in their own
subdirectories named for the underlying security. That was starting to look really
ugly. I imagined that I would run into even more trouble when it came to storing
warrants and intraday movements for a stock.
I looked around for alternatives. MySQL ([Link] has an embedded
database engine that is really fast, but this would have cost a ridiculous amount of
money for a royalty-free distribution license, or a determination that I would release
my entire project as open source. Hmmm ... not yet. Sleepcat
([Link] ) has Berkeley DB, which is a very fast and efficient
embedded database engine, so I had a look at that. Again, a lot of money, or open
source. They do have an old version (1.8.5) that is released under the BSD
distribution license and completely free. I played around with that for a bit, but as
various sites state, there are some well known bugs with it. I didn't really know
enough about the project to fix them. Just FYI: if you have a need for an embedded
database, and you meet the open source criteria (or personal use, blah blah blah...)
go with one of these packages :-)
So I was stuck. I didn't want a bzillion files floating around in the user's file system,
but I wanted the ability to add many records over time, and retrieve them quickly. I
needed some sort of database package, couldn't find one, so eventually I decided to
do it myself. Fine. So where to start? Back to my days of University, and the second
year Data Structures and Algorithms class. The text for this class was Cormen,
Leiserson and Rivest's excellent Introduction to Algorithms , 2nd Edition, MIT Press,
Mass., 1990. Although we didn't study B-Trees at the time, I remember trying to
implement one a bit later in an abortive attempt to break into the entertainment
industry. Long story ... don't ask. This time, though, I was determined to make it
work.
Oh ... why use a B-Tree? Well, they're kinda nice to use, since they allow storage of
large amounts of data on disk, indexed by key, with records accessible in roughly
O(log n) time where n is the number of nodes in the tree. There are many places you
find out more about B-Trees. I'm not inclined towards reproducing large slabs of the
text here, but you could look at [Link] if you are interested. It
includes the basic algorithms for creating, searching, and inserting records from
Cormen, Leiserson and Rivest.
Back to the task at hand, I knew that deletion would be a problem, since no-one
publishes pseudo-code for the deletion of keys from a B-Tree. It appears to be a bit
more complex than the other operations and is generally "left as an exercise for the
reader". Grr. So I researched other textbooks and I searched the net. Eventually I
found a paper entitled "Implementing Deletion in B+-Trees" by Jan Jannick of
Stanford University. To quote from the abstract: "There are published algorithms and
pseudo-code for searching and inserting keys, but deletion, due to its greater
complexity and perceived lesser importance, is glossed over completely or left as an
exercise to the reader. To remedy this situation, we provide a well documented
flowchart, algorithm, and pseudo-code for deletion, their relation to search and
insertion algorithms, and a reference to a freely available, complete B+-tree library
written in the C programming language." Yay! So I downloaded the code referred to
in the paper (you can get them starting from here). Except that the C code didn't
compile in VS7, and the C++ code broke after a couple of insertions. Bugger.
So, I built the creation, insertion and search code, etc. using the text's pseudo-code.
Unable to find any deletion pseudo-code elsewhere, I decided that I would just have
to bite the proverbial bullet and write the code based on the narrative provided. After
a long time, everything worked. I decided that no-one should have to go through
that again, so I'm making the code available for public distribution. This may
frustrate many university lecturers since there now exists code that actually does
this wretched delete, but somehow ... I struggle to care. Victory is mine!