It wasn't long before Alice found herself in front of a large building. It was a rather nondescript building but did have very elaborate screens over each window. "Hmmm, I wonder what this is? It sort of looks like a bank!" thought Alice as she entered the building. Inside was a lobby with a high counter and behind the counter a woman was busily sorting through a large pile of paper.
"May I help you?" she asked crisply as Alice walked up to the counter. "Do you wish to add or search for a record, or query the data base?"
"Well, I... I... I don't know." stammered Alice.
"Obviously, you must want to query, if you don't know."
"Is this a bank?"
"A bank? Does this look like a bank? Well, I guess it does, and some people call it that, but what I do here is much more useful."
"Then, is the data stored here?"
"...are the data...!"
Alice looked blank.
"Are the data stored here? Data are plural. Datum is singular! At least be syntactically correct." the woman replied haughtily.
"Uhhh, what is it I can query?" asked Alice rather hesitantly.
"You must have some idea! How in the world did you get to your age without...? Never mind! Programs these days!" she said shaking her head. "You can retrieve any data that are stored in the data base."
"I have never heard of a data base." said Alice. "Is it the bottom of the data?"
"Are you trying to be funny?" the woman asked with a frown. "No, I guess not," she finally said after looking intently at Alice for what seemed the longest time. "The data base is the collection of all the data, neatly organized to allow efficient manipulation, addition, deletion, and retrieval. There! Now you know!"
Alice still wasn't certain she knew. "How do I query?" she asked hesitantly.
"Well, do you have a key?"
"Never mind, you can make a general query, and I can tell you the result."
"Oh, you must be a teller?" said Alice with a smile.
"I am not a teller!" replied the woman very emphatically. "Why is it that everyone assumes that because I am a woman, I am just a teller? I am a data base manager!"
"Uhh, I didn't mean.... Where is, ah, are the data?" Alice asked, hoping that this question would change the subject.
"The data are stored in records, of course...."
"My sister has some music records, but I prefer tapes," interrupted Alice.
"Not those kind of records!"
"Oh. OH! You mean the highest, and biggest, and records like that!" Alice said brightly after thinking for a few seconds.
"Well, some of the records do contain rather extreme values, but in general they are rather ordinary."
"Where are the records?" asked Alice looking around and not seeing anything that to her looked like a record.
"They're in files of course." she rasped.
"Oh, now I understand!" exclaimed Alice with a smile. "My sister keeps all her papers in a file. She told me that there is a class she could take in filing to become a file clerk. Are you...."
"I am not a file clerk!" the woman answered rather icily. "Neither am I a manicurist! I am a manager. I have worked hard and studied long hours to get this job. I am as good, if not better, than any man who is a data base manager." She was almost shouting toward the end.
"Oh, I didn't mean to.... Of course, you are really quite professional. No one would mistake.... Is, I mean, are the data, er, the records, you... you manage stored in filing cabinets?" Alice wished that the woman would not be so angry with her.
"Hrumph, the records are stored in many different ways. Some are in sequential files, some in random files, some in trees...."
"Oh, I very much like trees!" interrupted Alice. "What kind of trees?"
"I manage many different trees."
"Do you plant the trees in the field? And take care of them?" she asked cheerily.
"Of course not! The fields are in the trees, actually, in the records in the trees, not the other way around!"
"That seems rather curious," replied Alice.
The woman looked at her for several seconds, then said, "You are the curious one—asking all these questions, and not making a data deposit or query. You'd better be careful. 'Curiosity killed the cat,....'"
"'But information brought it back!'" interrupted Alice with a smile which quickly faded when she saw the woman was not at all pleased. "You were saying that you manage different trees?"
"There are many kinds of trees. I take care of binary trees, multiway trees, B trees...."
"Oh, do those have honey?" Alice asked. "I just know that Pooh would like those!"
"No honey, honey!" she answered sarcastically. "Here, let me show you a whole forest." And she led her through a door into a large open area. When Alice saw the trees she felt very disoriented and almost ill.
"I have never seen trees like that!" she exclaimed. "They're all upside down!" And indeed the trees were growing downward from the ceiling of the huge room with large limbs branching into smaller ones, and at each end of the smallest twigs a single leaf.
"Nonsense! All trees grow this way."
"But trees grow up, not down," Alice protested. "And what if they fall on me?"
"Their roots hold them in place. Hmmm, maybe you will fall on them."
"But I'm standing on the floor."
"How do you know that you are not upside down?"
Poor Alice opened her mouth to reply, but realized that maybe in this room everything was indeed upside down, or maybe she was underground and seeing what trees looked like from below. That thought made her head spin, but she thought that she had seen even more unusual things that day. She finally asked, "You said that you store records in the trees?"
"Of course! Trees are very fast—that's why they are used for ASAP data."
"I never thought of a tree as being fast," said Alice. "They grow so slowly, and wave gently in the breeze...."
"Oh my yes! They are very fast and efficient," the woman replied. "But, of course, they are not as fast as a hash list."
"A hash list? A fast hash list? Is that a list of something to eat at a fast food restaurant?" asked Alice brightly.
The woman frowned, shook her head slowly, and said to herself but loud enough that Alice could hear, "Her code must have gone through a hash function." Then to Alice she added, "I suppose you think a linked list is a directory of hot dogs?"
Alice didn't really have a chance to respond, when the woman said, "Never mind!" And she led Alice out of the forest room back to the lobby where the counter was. "If you're so smart, why don't you try looking up something for yourself. There should be some keys you can use over there." And she pointed to a box.
Alice hesitated for a few moments trying to decide if she really wanted to look up something, then walked over and selected a huge key. "Do I use this to unlock the data base?" she asked as she returned to the counter and the data base manager.
"As far as I know you are the only user, hence the data base isn't locked. And besides, the key is used to find a record."
"How will I know when I have found what I am looking for?"
"Start at the very beginning, and go until the key matches!"
"You said there were so many records. This is going to take a long time." sighed Alice.
"It depends upon the data structure," replied the woman. "If the records are stored in a linked list or other sequential structure, then you will have to do a serial search...."
"My mother does that in the grocery store when we ask her to get something for breakfast!" Alice blurted out.
The woman paused, then said, "As I was saying before I was so rudely interrupted, ...and that may take a long time, but if the records are stored in a tree or hash list, then it will not take long at all."
"How will I know?" asked Alice rather subdued.
At this question, the woman gave a big grin and said, "Aha, you won't! Just give the key to the data base manager, and I will retrieve the records for you—you really don't have to know a thing about the way the data are organized!"
"I don't think I really need to find anything in this data base," decided Alice. "Thank you very much, but I must be going now." And with that she put the key on the counter and ran out the door.